Автоматные грамматики

     В неукорачивающих грамматиках при построении предложений языка цепочка символов заменяется на цепочку не меньшей длины.

     Эти два класса грамматик эквивалентны.

     При построении компиляторов такие грамматики не применяются, поскольку языки  программирования имеют более простую  структуру и могут быть построены  с помощью грамматик других типов.

3. Тип 2 – Контекстно-свободные (КС) грамматики

     Контекстно-свободные (КС) грамматики имеют правила вида A ® b, где AÎVN, bÎV⁺. В правой части у них стоит всегда хотя бы один символ.

     Такие грамматики еще называют неукорачивающими контекстно-свободными (НКС) грамматиками. Существует почти эквивалентный им класс укорачивающих контекстно-свободных (УКС) грамматик, отличие которого в том, что он допускает пустую цепочку, т.е. правила имеют вид A ® b, где AÎVN, bÎV^*. В дальнейшем, если возможность наличия в языке пустой цепочки не имеет принципиального значения, будем говорить просто о КС-грамматиках.

     КС-грамматики широко используются при описании синтаксических конструкций языков программирования.

4. Тип 3 – Регулярные грамматики

     К этому типу относятся два эквивалентных  класса грамматик: леволинейные и праволинейные.

     Леволинейные грамматики могут иметь правила двух видов: A ® Bg, или A ® g, где A,BÎVN, gÎVT⁺.

     Праволинейные грамматики имеют правила тоже двух видов: A ® gB, или A ® g, где A,BÎVN, gÎVT⁺.

     Регулярные  грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т.д. Они очень просты и удобны в использовании, поэтому в компиляторах на их основе строятся функции лексического анализа входного языка.

     Из  определения типов видно, что  любая регулярная грамматика является также КС-грамматикой, или любая  грамматика может быть отнесена к  типу 0. В то же время существуют УКС-грамматики, которые не относятся к типу 1, поскольку могут содержать правила вида A ® l, недопустимые в этом типе. В общем, сложность грамматики обратно пропорциональна тому максимально возможному номеру типа, к которому может быть отнесена эта грамматика. Самыми простыми являются грамматики типа 3, самыми сложными – типа 0. 
 

3.Автоматные грамматики

Язык, для  которого существует распознающий его  конечный автомат, называется автоматным языком.Они могут быть леволинейными и праволинейными.

   Леволинейные автоматные грамматики G(VT, VN, P, S) могут иметь правила двух видов: A ® Bt или A ® t, где A, BÎVN, tÎVT.

   Праволинейные автоматные грамматики могут тоже иметь правила двух видов: A ® tB или A ® t, где A,BÎVN, tÎVT.

   Как следует из приведенных правил, автоматные грамматики отличаются тем, что в  их правилах вместо цепочки терминальных символов присутствует только один терминальный символ. Очевидно, что любая автоматная грамматика является регулярной, обратное же справедливо не всегда.

   Конечно-автоматная грамматика, грамматика с конечным числом состояний - это грамматика бесконтекстная,  каждое правило которой имеет вид А→aB или A→a где A,B - вспомогательные символы,  а - один из основных символов (иногда допускаются также правила вида А→ Λ,  где Λ - пустая цепочка. Класс порождаемых языков при этом расширяется только за счет языков, получаемых из прежних добавлением цепочки Λ). Для каждой автоматной грамматики можно построить эквивалентный ей конечный автомат. Класс языков, порождаемых атоматные грамматики. (автоматных языков), совпадает (при допущении правил с пустой правой частью) с классом регулярных множеств. Автоматные языки образуют собственный подкласс класса линейных языков;так, линейный язык ǀn=1,2…} - не автоматный. Класс автоматных языков замкнут относительно объединения, пересечения, умножения, подстановки и усеченной итерации (а при наличии правил с пустой правой частью также и относительно итерации). Пересечение бесконтекстного языка с автоматным есть бесконтекстный язык.

   Для наглядного изображения автоматной грамматики используется диаграмма - ориентированный мультиграф, вершинами которого служат вспомогательные символы, и из вершины А в вершину ведет дуга, помеченная (основным) символом  а, если в грамматике есть правило кроме того, в диаграмме имеется еще одна вершина А→aB - заключительная, в которую из вершины - вспомогательного символа А - идет дуга, помеченная символом а, если в автоматной грамматике есть правило А→a. (При наличии правил вида А→ Λ каждый символ  А , для которого имеется такое правило, также считается заключительной вершиной.) Цепочка в основном словаре выводима в грамматике из вспомогательного символа А тогда и только тогда, когда она "записана" на некотором пути в диаграмме, идущем из А в заключительную вершину. На рис. изображена диаграмма автоматной грамматики с правилами I→aI, I→aB, B→bB, B→b (I - начальный символ,  К- заключительная вершина), порождающей язык ǀn,m=1,2…}

   Классы  обычных регулярных грамматик и  автоматных почти эквивалентны (т.е. с точностью до правила S ® l). В автоматных грамматиках разрешается правило вида S ® l, где S – целевой символ грамматики. При этом символ S не должен встречаться в правых частях других правил грамматики; тогда язык, задаваемый автоматной грамматикой G, будет включать в себя пустую цепочку: lÎL(G).

   Существует  алгоритм, позволяющий преобразовать  регулярную грамматику к автоматному  виду. Он очень полезен, т.к. упрощает задачу построения распознавателей  для регулярных языков. Кратко его  идея состоит в том, что при  наличии в правой части правила  регулярной грамматики цепочки терминальных символов длины n необходимо ввести n–1 дополнительный нетерминальный символ и записать для каждого из них соответствующие правила, т.е. разбить стоящую справа терминальную цепочку на символы и разнести их по разным правилам.

   Линейные  грамматики (праворекурсивные и леворекурсивные) называются автоматными грамматиками,  так  как  языки,  порождаемые  ими,  совпадают  с  языками,  распознаваемыми конечными автоматами.

   Рассмотрим  ряд теорем.

   Теорема. Для каждой праволинейной грамматики существует эквивалентный конечный автомат.

   Доказательство.  Каждому нетерминалу произвольной  праволинейной грамматики G поставим в соответствие одно состояние конечного автомата A. Добавим еще одно состояние -  единственное  конечное  состояние.  Состояние,  соответствующее аксиоме,  назовем начальным состоянием.  Каждому правилу A→aB  поставим  в соответствие  команду Aa  → B,  а каждому терминальному правилу A → a поставим в соответствие команду Aa → F. Таким образом, выводу цепочки в грамматике  S ⇒ a1A1  ⇒ a1a2A2  ⇒ ... ⇒ a1a2...ak-1Ak-1⇒ a1a2...ak  взаимно однозначно  соответствует последовательность команд построенного автомата A:  Aa1 → A1; A1a2 → A2; . . . ; Ak-1ak → F. Таким образом, язык L(G) = L(A).

   Пример. Пусть для заданной грамматики G требуется построить конечный автомат.

   S → aS | bB;

   A → aA | bS;

   B → bB | с | cA.

   Решение.  Граф  автомата  будет  иметь  четыре  вершины,  три  из  них  помечены нетерминальными символами  грамматики S, A, B, четвертая вершина, помеченная  символом F,  является  единственным  заключительным  состоянием.  Начальным  состоянием  является  вершина, соответствующая аксиоме S.

   Каждому правилу грамматики поставим в соответствие  команду конечного автомата: Sa → S -  в  начальном  состоянии  при  поступлении  на  вход  терминального  символа   а  автомат остается  в том же состоянии   S;

Sb  →  B -  из  начального  состояния   при  поступлении  на  вход  терминала b  автомат переходит  в состояние B; Bb → B - в состоянии  В при поступлении на вход  терминала b автомат остается  в том же состоянии B;

 Bc → F -  из  состояния В при поступлении на  вход  терминала c  автомат переходит в заключительное состояние F;

Bc →  A -  из  состояния В  при   поступлении  на  вход  терминала  c  автомат  переходит  в  состояние А; 

Aa →  A - в состоянии А при поступлении  на вход терминала а автомат  остается в этом же состоянии А;

Ab →  S -  из  состояния A  при   поступлении  на  вход  терминала  b  автомат  переходит  в  состояние  S. Полученный  недетерминированный  конечный  автомат  распознает  цепочки  языка,порождаемые праворекурсивной грамматикой G.

Теорема.  Для произвольного конечного автомата  существует  эквивалентная праволинейная грамматика.

Доказательство. Каждому состоянию произвольного автомата поставлен в соответствие нетерминал грамматики, причем начальному состоянию будет соответствовать аксиома. Тогда для каждой команды Ac → B в множество правил грамматики включим правило A→ cB,  причем  в  случае,  если B -  заключительное  состояние,  добавим  правило A  → c. Эквивалентность исходного конечного автомата и построенной грамматики очевидна. 
 
 
 
 
 
 
 
 
 
 
 
 
 

Заключение 

     Стремительное развитие вычислительной техники сделало  возможной компьютерную обработку  текстов, относящихся к самым  различным языкам – естественным языкам, языкам формул, языкам программирования.

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

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

     Литература 

1. Бильгаева Н.Ц.  «Теория алгоритмов, формальных  языков, грамматик и автоматов». Изд. ВСГТУ Улан-Удэ 2000г.
2. А.Н. Мелихов, В.И. Кодачигов «Теория алгоритмов и формальных языков» Таганрог 2006 г.
3. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс. – М.: Радио и связь, 1988.
4. Малявко А.А. Теория формальных языков / Учебное пособие, Ч.1,2,3. – Новосибирск: Изд-во НГТУ, 2001-2005.
5. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение / Учебник для вузов. – СПб.: Питер, 2001.
6. Н. Ю. Демин  Дискретная математика «О необходимом количестве правил автоматной грамматики, порождающей конечный язык». 2000г.