Для чего придумали формальные языки
Формальные языки и грамматики
Мотивация
Время от времени на Хабре публикуются посты и переводные статьи, посвященные тем или иным аспектам теории формальных языков. Среди таких публикаций (не хочется указывать конкретные работы, чтобы не обижать их авторов), особенно среди тех, которые посвящены описанию различных программных инструментов обработки языков, часто встречаются неточности и путаница. Автор склонен считать, что одной из основных причин, приведших к такому прискорбному положению вещей, является недостаточный уровень понимания идей, лежащих в основании теории формальных языков.
Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 50-х годов прошлого века и до наших дней, по этому научному направлению было выпущено всего две докторских диссертации. Одна из них была написана в конце 60-х годов Алексеем Владимировичем Гладким, вторая уже на пороге нового тысячелетия — Мати Пентусом.
Далее в наиболее доступной форме описаны два основных понятия теории формальных языков: формальный язык и формальная грамматика. Если тест будет интересен аудитории, то автор дает торжественное обещание разродиться еще парой подобных опусов.
Формальные языки
Коротко говоря, формальный язык — это математическая модель реального языка. Под реальным языком здесь понимается некий способ коммуникации (общения) субъектов друг с другом. Для общения субъекты используют конечный набор знаков (символов), которые проговариваются (выписываются) в строгом временном порядке, т.е. образуют линейные последовательности. Такие последовательности обычно называют словами или предложениями. Таким образом, здесь рассматривается только т.н. коммуникативная функция языка, которая изучается с использованием математических методов. Другие функции языка здесь не изучаются и, потому, не рассматриваются.
В качестве известного примера такой математической абстракции можно привести модель, известную под неблагозвучным для русского уха названием «мешок слов». В этой модели исследуются тексты естественного языка (т.е. одного из тех языков, которые люди используют в процессе повседневного общения между собой). Основной объект модели мешка слов — это слово, снабженное единственным атрибутом, частотой встречаемости этого слова в исходном тексте. В модели не учитывается, как слова располагаются рядом друг с другом, только сколько раз каждое слово встречается в тексте. Мешок слов используется в машинном обучении на основе текстов в качестве одного из основных объектов изучения.
Но в теории формальных языков представляется важным изучить законы расположения слов рядом друг с другом, т.е. синтаксические свойства текстов. Для этого модель мешка слов выглядит бедной. Поэтому формальный язык задается как множество последовательностей, составленных из элементов конечного алфавита. Определим это более строго.
Алфавит представляет собой конечное непустое множество элементов. Эти элементы будем называть символам. Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита — начальные строчные буквы латинского алфавита. Например, выражение V =
Цепочка представляет собой конечную последовательность символов. Например, abc — цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1. an — цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.
Наконец, формальный язык L над алфавитом V — это произвольное множеств цепочек, составленных из символов алфавита V. Произвольность здесь означает тот факт, что язык может быть пустым, т.е. не иметь ни одной цепочки, так и бесконечным, т.е. составленным из бесконечного числа цепочек. Последний факт часто вызывает недоумение: разве имеются реальные языки, которые содержат бесконечное число цепочек? Вообще говоря, в природе все конечно. Но мы здесь используем бесконечность как возможность образования цепочек неограниченной длины. Например, язык, который состоит из возможных имен переменных языка программирования C++, является бесконечным. Ведь имена переменных в C++ не ограничены по длине, поэтому потенциально таких имен может быть бесконечно много. В реальности, конечно, длинные имена переменных не имеют для нас особого смысла т.к. к концу чтения такого имени уже забываешь его начало. Но в качестве потенциальной возможности задавать неограниченные по длине переменные, это свойство выглядит полезным.
Итак, формальные языки — это просто множества цепочек, составленных из символов некоторого конечного алфавита. Но возникает вопрос: как можно задать формальный язык? Если язык конечен, то можно просто выписать все его цепочки одну за другой (конечно, можно задуматься, имеет ли смысл выписывать цепочки языка, имеющего хотя бы десять тысяч элементов и, вообще, есть ли смысл в таком выписывании?). Что делать, если язык бесконечен, как его задавать? В этот момент на сцену выходят грамматики.
Формальные грамматики
Способ задания языка называет грамматикой этого языка. Таким образом, грамматикой мы называем любой способ задания языка. Например, грамматика L =
Назначение грамматики — задание языка. Это задание обязательно должно быть конечным, иначе человек не будет в состоянии эту грамматику понять. Но каким образом, конечное задание описывает бесконечные совокупности? Это возможно только в том случае, если строение всех цепочек языка основано на единых принципов, которых конечное число. В примере выше в качестве такого принципа выступает следующий: «каждая цепочка языка начинается с символов a, за которыми идет столько же символов b». Если язык представляет собой бесконечную совокупность случайным образом набранных цепочек, строение которых не подчиняется единым принципам, то очевидно для такого языка нельзя придумать грамматику. И здесь еще вопрос, можно или нет считать такую совокупность языком. В целях математической строгости и единообразия подхода обычно такие совокупности языком считают.
Итак, грамматика языка описывает законы внутреннего строения его цепочек. Такие законы обычно называют синтаксическими закономерностями. таким образом, можно перефразировать определение грамматики, как конечного способа описания синтаксических закономерностей языка. Для практики интересны не просто грамматики, но грамматики, которые могут быть заданы в рамках единого подхода (формализма или парадигмы). Иначе говоря, на основе единого языка (метаязыка) описания грамматик всех формальных языков. Тогда можно придумать алгоритм для компьютера, который будет брать на вход описание грамматики, сделанное на этом метаязыке, и что-то делать с цепочками языка.
Такие парадигмы описания грамматик называют синтаксическими теориями. Формальная грамматика — это математическая модель грамматики, описанная в рамках какой-то синтаксической теории. Таких теорий придумано довольно много. Самый известный метаязык для задания грамматик — это, конечно, порождающие грамматики Хомского. Но имеются и другие формализмы. Один из таких них — окрестностные грамматики, будет описан чуть ниже.
Окрестностные грамматики
В середине 60-х годов советский математик Юлий Анатольевич Шрейдер предложил простой способ описания синтаксиса языков на основе т.н. окрестностных грамматик. Для каждого символа языка задается конечное число его «окрестностей» — цепочек, содержащих данный символ (центр окрестности) где-то внутри. Набор таких окрестностей для каждого символа алфавита языка называется окрестностной грамматикой. Цепочка считается принадлежащей языку, задаваемому окрестностной грамматикой, если каждый символ этой цепочки входит в нее вместе с некоторой своей окрестностью.
Не всякий язык может быть описан окрестностной грамматикой. Рассмотрим, например, язык B, цепочки которого начинаются либо с символа «0», либо с символа «1». В последнем случае далее в цепочке могут идти символы «a» и «b». Если же цепочка начинается с нуля, то далее могут идти только символы «a». Нетрудно доказать, что для этого языка нельзя придумать никакой окрестностной грамматики. Легитимность вхождения символа «b» в цепочку обусловлена ее первым символом. Для любой окрестностной грамматики, в которой задается связь между символами «b» и «1» можно будет подобрать достаточно длинную цепочку, чтобы всякая окрестность символа «b» не доставала до начала цепочки. Тогда в начало можно будет подставить символ «0» и цепочка будет принадлежать языку A, что не отвечает нашим интуитивным представлениям о синтаксическом строении цепочек этого языка.
С другой стороны, легко можно построить конечный автомат, который распознает этот язык. Значит, класс языков, которые описываются окрестностными грамматиками, уже класса автоматных языков. Языки, задаваемые окрестностными грамматиками, будем называть шрейдеровскими. Таким образом, в иерархии языков можно выделить класс шрейдеровских языков, который является подклассом автоматных языков.
Можно сказать, что шрейдеровские языки задают одно простое синтаксическое отношение — «быть рядом» или отношение непосредственного предшествования. Отношение дальнего предшествования (которое, очевидно, присутствует в языке B) окрестностной грамматикой задано быть не может. Но, если визуализировать синтаксические отношения в цепочках языка, то для диаграмм отношений, в которые превращаются такие цепочки, можно придумать окрестностную грамматику.
Зачем люди придумывают языки?
На земном шаре люди говорят более чем на 6000 естественных языков; кроме того, существует множество мертвых. Казалось бы, какое вавилонское разнообразие! Но тем не менее находятся энтузиасты, которые разрабатывают новые языки. Зачем они это делают?
Когда заходит речь об искусственных языках, первым делом вспоминают эсперанто. Созданный в 1887 году, эсперанто процветает по сей день — на нем свободно разговаривают сотни тысяч человек во всем мире. Подобное назначение искусственных языков — для международного общения — наиболее очевидное, но не единственное и даже не самое распространенное.
Языки для международного общения
Популярность эсперанто не случайна — он действительно прост (всего 16 правил без единого исключения) и понятен, по крайней мере, для европейцев и американцев, поскольку содержит в основном латинские и вообще европейские корни слов, в том числе и славянские.
Подобные языки, с собственной грамматикой и корнями, взятыми из естественных языков, называются «апостериорными» (лат. «из последующего»), в отличие от «априорных», для которых слова придумывали искусственно. Языки для международного общения часто называют «вспомогательными», так как они не имеют целью заменить основные языки (хотя когда-то встречались и такие честолюбивые устремления); иногда слово «искусственные» заменяют словом «плановые», чтобы избежать негативной коннотации; наконец, собственно языками принято считать лишь те из них, которые получили достаточно широкое распространение, а если свободно говорит только сам автор да пара его друзей, и те со словарем, то это не язык, а «лингвопроект».
Эсперанто быстро получил широкое распространение, но он не был первым в своем роде — вторая половина XIX века отмечена пристальным интересом к искусственным «универсальным» языкам, так что плод трудов Лазаря Заменгофа был взращен на плодородной почве. А первый зафиксированный искусственный язык — Lingua Ignota («речь неведомая») — был создан и описан аббатисой Хильдегардой Бингенской еще в XII веке, которая считала его ниспосланным свыше. Lingua Ignota имела собственную письменность и глоссарий из тысячи слов, ранжированных от божественных понятий до нижайшего слова «сверчок». Существовал свой искусственный язык и на мусульманском Востоке — он назывался «бала-ибалан» и был разработан на основе арабского, персидского и турецкого шейхом Мухиеддином.
В 1817 году француз Жан Франсуа Сюдр представил общественности донельзя странную выдумку: язык сольресоль, слова которого (в основном словаре их насчитывалось 2660) состояли из названий музыкальных нот. Сложно поверить, что изначально затея была чем-то большим, нежели интеллектуальной игрой, но новый язык оказался пригодным для международного общения (музыкальная нотация интернациональна) и потому удостоился наград и признания современников. Слова сольресоля можно было произносить обычным образом, играть на музыкальных инструментах, записывать (изначально с помощью всего семи букв или цифр; впоследствии энтузиасты разработали специальную азбуку), рисовать семью основными цветами, отмахивать семафорными флажками и т. д.
Во второй половине XIX века популярность сольресоля сошла на нет и на смену ему пришли другие искусственные языки, менее вычурные и более удобные для общения. Их существовало довольно много: универсалглот (1868), волапюк (1880), пасилингва (1885), эсперанто (1887), лингва католика (1890), идиом-неутраль (1893–1898). Волапюк был довольно странен: он содержал корни, производные от европейских, — сильно искаженные, но все-таки узнаваемые, а потому большинству европейцев речь на волапюке казалась смешной (до сих пор это слово в переносном смысле означает тарабарщину). Впрочем, своих поклонников он нашел и был популярен в Германии вплоть до прихода к власти нацистов. В противоположность ему идиом-неутраль строился из чистых лексем основных языков Европы (русского, английского, немецкого, французского, итальянского, испанского и латыни), чтобы быть понятным «любому образованному человеку». Эсперанто создавался по подобному же принципу.
Создание новых языков продолжалось и в XX веке — омо (1910), окциденталь (1922), интерлингва (1936–1951) и другие — но ни один из них даже не приблизился по востребованности и распространению к эсперанто. Интересно отметить, что при этом от самого эсперанто отпочковывались производные «диалекты». Дело в том, что на первом конгрессе эсперантистов в 1905 году было решено считать правила, включенные Заменгофом в книгу «Основы эсперанто», незыблемыми — и с этого момента язык мог только расширяться, а базовая грамматика пребывала неизменной. Тем, кого не устраивали эти правила, оставалось только одно — создавать свой собственный лингвопроект. Уже в 1907 году случился первый раскол, связанный с возникновением сильно переработанной версии эсперанто — идо. За создателями нового языка последовало около 10% тогдашнего сообщества эсперантистов. Появлялись и другие клоны эсперанто: универсаль, эсперантидо, новиаль, нэо, но и они не получили существенного распространения.
Завершая рассказ о международных искусственных языках, нельзя не упомянуть такое явление, как «зонально сконструированные языки», понятные для представителей родственных народов или ограниченного географического региона. В качестве примера можно назвать африхили (народы Африки) и панславянские лингвопроекты словио и словянски. Вот пример текста на словио с официального сайта разработчиков: «Што ес Словио? Словио ес новйу межународйу йазика ктор разумийут чтирсто милион лудис на целойу земла!» Смешно, но понятно.
Воссоздание мертвых языков
Если создание новых языков — это процесс, устремленный в будущее, то в прошлом человеческой речи лежат языки мертвые, звуки которых никто не слышал тысячелетиями. Наука лингвистическая компаративистика занимается изучением законов, по которым развиваются языки. Кропотливо, как палеонтолог воссоздает по единственной косточке облик реликтового животного, она «оживляет» мертвые языки, заставляя вновь звучать древние слова.
С XIX века лингвисты занимаются реконструкцией праиндоевропейского языка, на котором говорили 5000 лет назад общие предки германцев, кельтов, славян и множества других народов. В 1868 году немецкий ученый Август Шлейхер написал на праиндоевропейском — каким он был восстановлен к тому времени — басню «Овца и кони». На протяжении полутора столетий представление o праиндоевропейском языке менялось — и басню Шлейхера неоднократно переписывали более «правильно».
А в 2006 году двое энтузиастов из Испании на основе восстановленного праиндоевропейского создали искусственный «новый индоевропейский» язык. Амбиции у них грандиозные: сделать индоевропейский главным официальным языком Евросоюза.
Фантастические языки
Знатокам творчества Джона Рональда Руэла Толкина известно, что его Средиземье начиналось не с мифологии эльфов, не с географии и вовсе не с сюжета о Кольце, а с вымышленных наречий. Лингвист и полиглот, знавший более десяти языков, Толкин с детских лет находил удовольствие в звучании речи — родной и чужой. В качестве хобби он в свободное время начал конструировать языки, руководствуясь совершенством и благозвучием, и лишь потом эстетический процесс перетек в создание фантастического мира и существ, для которых придуманные языки могли бы быть естественными.
Сейчас многие авторы, пишущие в жанре эскапистского фэнтези, подражая Толкину, создают наречия для своих выдуманных народов, как правило, проработанные весьма поверхностно — исключительно для того, чтобы передать экзотичность.
Впрочем, функция вымышленных языков в художественных произведениях может быть не только антуражной. Гипотеза Сепира–Уорфа (о ней «Популярная механика» писала в №2, 2012) предполагает, что носители языков, особенно принадлежащие к далеким друг от друга культурам, мыслят по-разному, а элементы таких языков далеко не всегда транслируются друг в друга без искажений. Таким образом в фантастическом произведении можно передать иной склад мысли негуманоидной расы или общественной формации.
Джордж Оруэлл для своей антиутопии «1984» придумал (правда, разработал его не целиком) «новояз» — искусственный язык, созданный на основе английского и имеющий целью воздействовать на мышление людей, формируя его определенным образом — в частности, делая невозможным оппозиционный способ мышления. Вообще антиутопии и социальная фантастика, обращенная к будущему, — благодатная почва для подобных лингвистических экспериментов. К искусственным языковым концепциям обращались Евгений Замятин («Мы») и Энтони Бёрджесс («Заводной апельсин»). Роберт Хайнлайн описал в повести «Бездна» искусственный язык «спидток», использующий множество звуков и весьма ограниченный набор слов.
Американский лингвист Марк Окранд по заказу Paramount Pictures разработал язык для одной из инопланетных рас сериала Star Trek — клингонов. За основу он взял несколько языков индейцев Северной Америки и санскрит. В клингонском много звуков, нехарактерных для английского: «тлх», «кх», «ы», гортанная смычка; письменность сделана на базе тибетского алфавита. Грамматика языка также весьма специфична, благодаря чему он воспринимается действительно как чужой. Клингонский язык получил распространение среди поклонников сериала — в настоящее время на нем способны изъясняться несколько сотен человек, существует Институт клингонского языка, который издает периодику и переводы литературной классики, есть клингоноязычная рок-музыка и театральные постановки, а также раздел поисковой системы Google.
Другой лингвист, профессор Университета Южной Калифорнии Пол Фроммер, на основе полинезийских языков создал на’ви — язык синекожих аборигенов планеты Пандора из фильма «Аватар». Поклонники фильма охотно изучают на’ви и объединяются в группы, чтобы общаться между собой. И таких примеров, когда для художественного произведения конструируется полноценный язык, довольно много: Дэвид Петерсон разработал дотракийский язык для сериала «Игра престолов» по романам Джорджа Мартина — и им сразу же заинтересовались поклонники; язык Д’ни, созданный для компьютерных игр Myst Ричардом Уотсоном, тоже вышел за пределы вымышленной вселенной.
Конструирование языков как хобби
Есть люди, для которых придумывание языков не имеет прикладного значения, это просто увлечение, игра. Чаще к такому времяпрепровождению склонны лингвисты, но иногда и простые смертные без специального образования вдруг начинают произносить странные сочетания звуков, а потом закапываются в труды по сравнительному языкознанию. Всё-таки, для того чтобы создать хоть сколько-нибудь полноценный язык, требуется понимать, как вообще функционируют языки, как развиваются, какие приемы встречаются в экзотических, не родных тебе наречиях, — да и вообще, чтобы иметь вкус к чему-либо, нужно неплохо в этом разбираться.
Увлечение странное, но сообщество людей, создающих «конланги» (от constructed languages, «сконструированные языки», себя же они называют, соответственно, «конлангерами»), весьма многочисленно. Только американское «Общество конструирования языков» (LCS) насчитывает тысячи участников (кстати, президент LCS — это упоминавшийся уже Дэвид Петерсон, а другой член общества, Билл Уэлден, консультировал создателей кинотрилогии «Властелин колец»). Подобного рода объединения существуют по всему миру. Счет искусственных языков также идет на тысячи. Разумеется, подавляющее большинство их могут свободно использовать только авторы и незначительный круг приближенных к ним людей — то есть терминологически это не языки, а лингвопроекты.
Язык жестов северо-американских индейцев
Наверняка многие помнят из фильмов и приключенческих книжек, что индейцы, когда не могли объясниться с собеседником — будь то европейский траппер или представитель другого племени — с помощью слов, переходили на язык жестов. Такой язык, схожий с современными языками жестов, действительно существовал: на огромной территории Великих Равнин его знали сотни тысяч человек. Он был весьма развит и ненамного уступал по информативности обычной устной речи. Его использовали в самых разных случаях: для меновых сделок, переговоров, обмена охотничьими и военными сведениями; впоследствии его освоили многие колонисты, имевшие дело с индейцами.
Языки для экспериментов
Искусственные языки лишены сложностей, противоречий, исключений и других недостатков, присущих стихийно развивавшимся естественным языкам, а потому могут быть платформой для всевозможных лингвистических, психологических, философских и прочих экспериментов. Фактически искусственный язык — это некая программируемая среда, в которую его создатель может заложить любые функции и значения переменных.
Простейший, и тем интересный, из искусственных языков называется «токипона», его создатель — полиглот Соня Элен Киса. В токипоне всего 120 корней из 14 букв, а грамматика и синтаксис несложные. Вследствие такой простоты большинство слов имеют очень широкий спектр значений; людям, говорящим на этом языке (а их сейчас насчитывается несколько сотен человек), приходится творчески подходить к построению фразы и в зависимости от контекста выбирать те или иные определения, необходимые для понимания. Например, в токипоне нет слова «собака», есть только общее слово soweli для всех наземных млекопитающих, поэтому в зависимости от ситуации придется уточнять, о ком именно идет речь: о милом щенке («смешное маленькое животное»), о кусачем и брехливом барбосе («плохое громкое животное») и т. д.
Если токипона — чрезвычайно многозначный язык, то созданный в 1955–1960 годах логлан — полная его противоположность. Это язык, абсолютно лишенный двусмысленностей, полностью логический, как и следует из его названия (loglan = logical language). Поначалу его непросто освоить, он требует определенного склада ума и привычки, но впоследствии у говорящих на этом языке проявляется склонность к необычным сравнениям и характеристикам, к словотворчеству. В 1987 году в результате разногласий среди лингвистов появился новый язык ложбан, практически аналогичный логлану по грамматике, но с отличающимся словарем. Когда, наконец, будет создан искусственный интеллект, для взаимодействия с ним более всего подойдут именно эти два языка.
А вот для контакта с внеземными цивилизациями предназначен язык линкос, созданный профессором математики Хансом Фройденталем. Как и логлан, он строго логичен, так же не содержит противоречий и исключений, но в нем нет и звуков. Информация кодируется любым удобным способом (например, двоичным кодом). Разрабатывая линкос, профессор Фройденталь исходил из двух предположений: что иные цивилизации могут отличаться от человека чем угодно, кроме наличия разума, и что математика универсальна.
Ну и наконец, вернемся к Роберту Хайнлайну, вернее, к его идее языка, близкого по скорости к мышлению. Если писатель-фантаст обозначил основные принципы такого языка, то лингвист Джон Кихада дал им дальнейшее развитие и воплотил в жизнь. Созданный им язык ифкуиль для увеличения информационной емкости речи использует не только обширный набор звуков (в его алфавите 136 букв), но и сложную необычную грамматику и множество организационных принципов, позаимствованных из лингвистики, математики и психологии. Так, фраза на ифкуиле oumpeа аx’ааluktеx переводится на русский как «наоборот, у меня такое чувство, что может оказаться, эта неровная высокая цепь гор, о которой идет речь, заканчивается где-то там»; само название языка iţkuîl обозначает «гипотетическая композиция разнообразных высказываний, сосуществующих в кооперативном единстве». Этим же длинным словосочетанием можно охарактеризовать и данную статью.