Контекстно-свободные грамматики. 
Языковые способности человека по Хомскому

Контекстно-свободные грамматики имеют правила вида: A —> alpha. В левой части правила должен стоять один символ (конечно, нетерминальный), а справа может быть любая цепочка из терминальных и нетерминальных символов (в том числе и пустая).

КС-грамматики задают два вида синтаксических отношений: отношение «быть рядом» и отношение «быть частью» или отношение иерархии. Отношение иерархии наиболее естественно для человеческого ума. Человеку свойственно типизировать вещи, т. е. рассматривать конкретные объекты своего мышления как части какого-то общего типа (класса). Каждая вещь, о которой думает человек, является экземпляром некоторого класса. Например, конкретный стул является экземпляром класса «стул» с соответствующими признаками. Человеческому уму также свойственно разделять типы на подтипы, двигаясь от более конкретных типов к более абстрактным. Скажем, стул есть подтип типа мебель, мебель есть подтип типа предмет, предмет есть подтип типа объект и т. п. Отношение «тип-подтип» и есть отношение иерархии.

КС-грамматика может быть проинтерпретирована как категориальная грамматика, т. е. грамматика типов. Символы грамматики в этом случае могут мыслиться как типы, а правила тогда задают отношение иерархии между типами. Нетерминальные символы выступают как сложные типы, а терминальный символы — как атомарные типы, у которых не может быть подтипов. Такая интерпретация КС-грамматики очень популярна и часто используется при создании трансляторов языков. Но, задавая класс КС-грамматик, Хомский имел ввиду нечто другое.

Ввиду того, что КС-грамматика является порождающей, она задает алгоритм (строго говоря, не алгоритм, но исчисление — многовариантный алгоритм) порождения цепочек языка. Порождение здесь задается не только присоединением цепочек справа или слева имеющейся цепочки, но и вставкой цепочки куда-нибудь внутрь имеющейся. Вставка производится заменой нетерминального символа в цепочке на цепочку, которая стоит в правой части некоторого правила, в левой части которого находится этот нетерминал. Скажем, цепочку aabBBACbbb можно преобразовать в цепочку aabBBaaaCbbb, если есть правило A —> aaa. В этом смысле, порождаемая цепочка растет не равномерно с какого-то края, но как-бы «пухнет» изнутри.

Проиллюстрируем сказанное на примере.

Рассмотрим язык.

L = {a^n b^n | n = 1, 2, 3,…}.

Выражение a^n здесь означает повторение n раз символа a. Таким образом, язык L состоит из цепочке вида ab, aabb, aaabbb и т. д. Зададим КС-грамматику для этого языка. Для этого заметим, что из цепочки языка можно получить другую цепочку языка, присоединяя к первой слева символ a, а справа символ b. Скажем, если имеется цепочка aabb, то из нее можно получить цепочку aaabbb. Это замечание дает правило порождения S —> aSb (напомним, что цепочки языка порождаются из начального нетерминала грамматики и, значит, могут быть обозначены этим символом). Есть еще специальный случай цепочки, которая не дробится на более мелкие — это цепочка ab. Введем для ее порождения правило S —> ab. Итак, грамматика языка имеет правила:

S —> aSb и S —> ab.

Зададим порождение цепочкиaaabbb:

S => aSb => aaSbb => aaabbb.

Контекстно-зависимые грамматики и грамматики без ограничений В правилах КС-грамматики нетерминальный символ в левой части правила порождения можно менять на правую часть в любом месте порождаемой цепочки, где бы этот символ не встретился. Но иногда хотелось бы различать контексты, в которых находится символ в цепочке, и в одних случаях производить замену символа, в других — нет. Правила КС-грамматики этого делать не позволяют, поэтому для таких случаев необходимы правила специального вида.

Контекстно-зависимая грамматика имеет правила вида w' A w'' —> w' alpha w''. Здесь w' и w'' — цепочки (может быть пустые), составленные из терминальных и нетерминальных символов грамматики, alpha — непустая цепочка из тех же символов. Иначе говоря, нетерминальный символ Aзаменяется на цепочку alpha в контексте цепочек w' и w''.

С КЗ-грамматикой связан другой класс грамматик — неукорачивающие грамматики. Правила в таких грамматиках должны удовлетворять одному условию: длина правой части должна быть не меньше длины левой части. Так как в правилах КЗ-грамматик имеется условие, чтобы цепочка alpha была непустая, то эти грамматики также являются неукорачивающими. Но, самое интересное состоит в том, что для каждого языка, заданного неукорачивающей грамматикой, может быть придумана КЗ-грамматика, задающая тот же язык. Иначе говоря, классы языков, задаваемых КЗ-грамматиками и неукорачивающими грамматиками, совпадают.

Зачем так необходимо выделять класс языков, задаваемых неукорачивающими грамматиками? Дело в том, что для таких языков можно задать распознающий автомат. Распознающая грамматика конструируется следующим образом: получая на вход цепочку, последовательно делаем порождения, упорядочивая их по длине порождаемой цепочки. Т.к. грамматика неукорачивающая, то таких порождений будет конечное множество и, если среди них не нашлось совпадения с данной на вход цепочкой, то напечатать «нет».

Для грамматики без ограничений на вид правил такой алгоритм распознавания в общем случае построить нельзя. Порождаемая цепочка может вести себя как «гармошка», раздуваясь и сдуваясь в процессе порождения. Поэтому достижение порождаемой цепочкой определенной длины не гарантирует, что далее в процессе порождения не будет получена поданная на вход цепочка.

Действительно ли КЗ-языки образуют собственный класс, не совпадает ли этот класс с классом КС-языков. Иначе говоря, есть ли язык, для которого гарантировано нельзя задать КС-грамматику, но можно задать КЗ-грамматику? Ответ: да, такие языки есть. В качестве примера такого языка можно привести следующий язык.

L = {ww}.

Цепочки этого языка составлены из двух повторяющихся цепочек над каким-то алфавитом. Доказывать, что для этого языка нельзя построить КС-грамматики мы здесь не будем. КЗ-грамматику можно задать на основе следующего соображения. Сначала сгенерировать цепочку w и нетерминальный символ, скажем A, т. е. получить цепочку Aw. Затем продвинуть символ A сквозь цепочку w, генерируя по ходу копии символов этой цепочки, после чего продвинуть эти символы направо. Примерно то же, как это будет реализовано в примере ниже.

Рассмотрим пример задания грамматики для языка.

L = {a^n² | n = 1, 2, 3, …}.

Цепочки этого языка состоят из символов a, причем число этих символов есть квадрат натурального числа: 1, 4, 9, 25 и т. д. Мы зададим для этого языка грамматику без ограничений. Генерация цепочек будет состоять из следующих этапов:

Генерация n символов для некоторого натурального числа n.

Порождение из этого числа символов n² символов.

Преобразование этих символов в символы a.

Для реализации первого этапа добавляем правила.

S —> LS’R.

S' —> AS’B.

S' —> AB.

Первым правилом оборачиваем порождаемую цепочку в ограничители L и R. Они нам понадобятся в дальнейшем для реализации третьей фазы генерации. Оставшиеся два правила просто генерируют цепочку вида AA… ABB…B, где число символов A и B совпадает.

Теперь необходимо породить n² символов на основе цепочке AA… ABB…B. Это делает простым приемом. Двигаем символы B налево и, при каждом переходе через символ A, порождать еще один символ C. Через символы C символ A может свободно проходить направо, а символ B — налево. Правила для этого этапа следующие:

AB —> BAC.

AC —> CA.

CB —> BC.

Когда все символы B дойдут до левого края, перейдя символы A, символов Cбудет ровно n².

Теперь надо освободиться от символов L, A, B и R, а также преобразовать символы C в символы a. Для этого аннигилируем символ B при его проходе до левого края, т. е. до символа L. Соответственно поступаем и с символом A на правом крае. При реализации такой стратегии останется цепочка видаLCC… CR. Чтобы избавится от символов L и R, начинаем двигать левый ограничитель к правому и, при их соприкосновении, уничтожаем эти символы. Заодно, при прохождении через символы L, преобразуем их в символы a.

Приведем правила для этой фазы генерации.

LB —> L.

AR —> R.

LC —> aL.

LR —> epsilon.

Здесь epsilon обозначает пустую цепочку.

Приведем в качестве примера порождение цепочки aaaa:

S => LS’R => LAS’BR => LAABBR => LABACBR => LBACACBR => LACACBR => LACABCR => LACBACCR => LABCACCR => LBACCACCR => LACCACCR => LCACACCR => LCCAACCR => LCCACACR => LCCACCAR => LCCACCR => LCCCACR => LCCCCAR => LCCCCR => aLCCCR => aaLCCR => aaaLCR => aaaaLR => aaaa.