Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Относительно языков, допускаемых ЛО-автоматами, имеет место следующее
Предложение. Для всякого ЛО-автомата % можно построить неукорачивающую грамматику G, такую, что L(G)=L(sH).
Доказательство. В качестве терминального словаря Vr грамматики G мы возьмем алфавит автомата Я, а в качестве ее вспомогательного словаря — множество
V0a = [Alh S, Т, #},
где
') Таким образом, ЛО-автомат — это не что иное, как недетерминированная Машина Тьюринга (перемещение головки, очевидно, равносильно использовавшемуся в гл IV перемещению ленты), на которую наложено дополнительное ограничение: в процессе работы не увеличивать длину рабочей цепочки Именно Для этого нужны окаймляющие цепочку маркеры, сохраняющиеся в течение всего вычисления. — Прим ред. 198
Часть II. Некоторые замечательные классы языков
. Aij сопоставляется ситуации (ait S,);
..S— аксиома грамматики G (новый символ);
... T — еще один новый вспомогательный символ; .... ф — маркер, с помощью которого отмечаются начало и конец цепочки.
Правила грамматики G определенным образом связаны с ситуациями автомата Я: они выполняют его вычисления, но только в обратном направлении — справа налево. Эти правила распадаются на три группы:
I. Правила группы I порождают цепочки вида
ф TAlf,
где и Aif соответствует заключительной ситуации (аг-, S/).
Эти правила таковы:
S ТАц для всякой заключительной ситуации (а{, Sf);
T-^Tal ]
т [ для всякого аг.
1 —> аг )
II. Правила этой группы перерабатывают цепочки, порожденные правилами группы I; их выполнение приводит к терминальной цепочке тогда и только тогда, когда 51 допускает эту цепочку. Проверка допустимости цепочки заканчивается, когда получена ситуация (аи S0), т. е. с выработкой символа А,:о.
. Команде (ui, Sj) -+(Sfi, ai, +1) соответствуют правила агАгь ->
Aijar для всякого ат є W
.. Команде (ait Sj) (Sb,ai,—1) соответствуют правила Arkai -*- arAij для всякого ат є W
... Команде (au Sj) (Sb, ab 0) соответствует правило Aui-* Aij.
III. Правила группы III позволяют завершать выводы. Они имеют вид
# Аго-*#аг.
Ясно, что L(G) = ?(?). При этом G — неукорачивающая грамматика специального типа: левые и правые части ее правил имеют длину 1 или 2.
12.2.4. НС-грамматики и JIO-автоматы
Можно доказать и обратное утверждение: для всякой неукора-чивающей грамматики можно построить JIO-автомат — вообще говоря, недетерминированный, — допускающий тот же язык.
Идея построения этого автомата состоит в том, что он должен искать в перерабатываемой цепочке вхождения правых частей правил грамматики (помечая принадлежащие этим вхождениям символы какими-либо метками), а затем, найдя такое вхождение, заменять его, символ за символом, вхождением левой части того же правила; при Этом длина цепочки не увеличится, так как левая Гл. XII. Грамматики непосредственно составляющих
199
часть не длиннее правой. Автомат допустит те и только те цепочки, которые он сможет таким способом переработать в аксиому.
Теперь из результата предыдущего пункта с учетом теоремы п. 12.1.4 получается следующая
Теорема (Курода — Ландвебер). Класс языков, порождаемых НС-грамматиками (класс НС-языков), совпадает с классом языков, допускаемых недетерминированными Л О-автопатами.
Неизвестно, совпадает ли этот класс с классом языков, допу» скаемых детерминированными ЛО-автоматами.
12.2.5. Некоторые свойства НС-языков
Можно доказать, что класс НС-языков замкнут относительно объединения, пересечения, умножения и итерации. Замкнут ли он относительно дополнения, неизвестно.
В то же время класс языков, допускаемых детерминированными ЛО-автоматами, образует булеву алгебру.
12.2.6. Алгоритмические проблемы
Почти все интересные алгоритмические проблемы для НС-грамматик рекурсивно неразрешимы; в частности, неразрешимы проблемы распознавания пустоты, конечности, бесконечности и «контекстной свободности» языка, порождаемого данной НС-грамматикой.
§ 12.3. КЛАССИФИКАЦИЯ АВТОМАТОВ
12.3.1. Линейно ограниченная память
Термин «линейно ограниченный автомат», предложенный Дж. Майхнллом '), объясняется тем, что в ходе вычислений такой автомат использует память ограниченного объема.
В предыдущих главах мы рассмотрели три класса автоматов: машины Тьюринга, автоматы с магазинной памятью, конечные автоматы.
Машина Тьюринга располагает на своей ленте неограниченным запасом пустых ячеек, благодаря чему она может запомнить неограниченное число символов. Конечный автомат, напротив, использует память конечного и, более того, фиксированного объема, полностью «умещающуюся» в управляющем устройстве: лента служит здесь исключительно для считывания данных (писать на ней нельзя).
ЛО-автоматы занимают промежуточное положение: объем их памяти не является раз навсегда фиксированным, но и не является неограниченным: он ограничен длиной обрабатываемой цепочки. Что же касается МП-автоматов, то они характеризуются ограниче-
') См. Майхилл [1960]. — Прим. ред. 200
Часть II. Некоторые замечательные классы языков
