Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Формальные свойства грамматик
'179
водах, производимых «копирующим устройством», описанным в примере (13), имеются строки, в которых заменяемый символ отстоит сколь угодно далеко и от самого правого, и от самого левого нетерминального символа.
При рассмотрении этих вопросов важно не терять из виду того, что вопрос, является ли данная контекстная грамматика строго контекстной, является неразрешимым, как указал Шамир [71).
В разд. 1.6 мы показали, что для каждого автомата PDS M существует преобразователь Т, обладающий следующим свойством: T преобразует вход х в цепочку у, которая сводится к е тогда и только тогда, когда M допускает х. Теперь мы видим, что, следовательно, для любой бесконтекстной грамматики G существует преобразователь Т, который преобразует х в цепочку у, сводящуюся к е тогда и только тогда, когда G порождает х. Однако можно получить несколько более сильный результат, проведя построение T непосредственно из G.
Определим модифицированную нормальную грамматику как нормальную грамматику, в которой нет пары правил вида А-і-ВС, D->-CE ни для каких нетерминальных Л, В, С, Dt Е\ т.е. в модифицированной нормальной грамматике для каждого нетерминала ного символа можно однозначно определить, появляется ли он в левой нли в правой ветви вывода (никакой нетерминальный символ не появляется и в левой, и в правой ветви). Очевидно, существует модифицированная нормальная грамматика, эквивалентная любой нормальной грамматике, а значит, и любой бесконтекстной грамматике.
Допустим, что мы теперь хотим применить конструкцию, аналогичную построению команд (18) и (19), к модифицированной нормальной грамматике G и получить преобразователь Т. Для каждого нетерминального символа Л из G преобразователь T будет иметь два состояния A1 и Ar Кроме них, T имеет начальное состояние S и команды (e,S)->-(S[, е) и (е, 5,)->(1,о'), где 5 —начальный символ G. Входным алфавитом T является терминальный словарь W грамматики G. Его выходной алфавит содержит, кроме того, символ а’ для каждого a ^ Vt , пару символов Л, Л' для каждого нетерминального Л из G и пару я, сг'. Если А-*а (a?W) естьправило G1 то T будет иметь команду
(а, Л() -» (Ar, Aaa'А'), (25)
если Л-5-SC есть правило G, то T будет иметь команды (е, A1) -> (B1, А),
(е, Br) - (С,, с), (26)
(е, Cr) -*¦ (Аг, А\
12*
180
И. Хомский
Так построенный преобразователь T будет обладать всеми основными свойствами преобразователя, сопоставленного устройству PDS прн помощи построения, приведенного в разд. 1.6, а именно G порождает х тогда и только тогда, когда T преобразует х в цепочку у, сводящуюся к е последовательным выбрасыванием пар а а’. Например, если G такова, как в примере (20), и T имеет на входе цепочку #aacbb# (с выводом как на рис. 9), T будет работать в основном так же, как M из (24), и закончит работу цепочкой
оSCAaa' A’ SCAaa' A' Scd S' С' Bbb' B' S' С' Bbb' В’ S' а', (27)
сводящейся к е, на ленте памяти.
Расширим теперь понятие «сводимости» и определим К как класс цепочек в выходном алфавите Ao > которые сводятся к е последовательным сокращением пар аа'или а'а(а, а' ? A0 ). То есть мы теперь рассматриваем а*' просто как обратные элементы в свободной группе 0 с образующими а ? Ao . Поскольку грамматика G, исходя из которой был построен Т, была модифицированной нормальной грамматикой, выходная цепочка T в действительности никогда не будет содержать подцепочек вида а'хг, где* сводится к е. Поэтому это расширение понятия «свэдимости» не приведет ни к каким осложнениям, и при этом преобразователь T сохраняет то свойство, что G тогда и только тогда порождает х, когда T преобразует х в цепочку у, сводящуюся к е.
' При этом изложении мы все время предполагали, как это и естественно (ср. с разд. 4 предыдущей главы), что словарь V, в котором строятся все бесконтекстные грамматики, есть фиксированное конечное множество символов, так что к представляет собой некоторый фиксированный язык в словаре V', состоящем из всех символов V, пары а, а' и символа а' для каждого а ? V. Пусть 9 — гомоморфизм (т.е. преобразование, осуществляемое с одним состоянием), такой, что cf(a)-».a для всех a ? VV и <р(л) =е для o fVT • Пусть U — множество всех цепочек в V. Заметим теперь, что если GnT таковы, как было описано выше, а L(G) — язык, порождаемый G, мы имеем, в частности, что L(G)='?IKГ) T(U) ].
Это непосредственно приводит к построению автомата PDS, допускающего К; следовательно, по теореме 6 разд. 1.6 К есть бесконтекстный язык. Как было отмечено в разд. 1.6, T(U) есть регулярный язык. Ниже будет явно показано, что пересечение бесконтекстного языка с регулярным языком является бесконтекстным языком и что преобразование переводит бесконтекстный язык в бесконтекстный (разд. 4.6). Если К и <р таковы, как в предыдущем абзаце, определим ^(L) для любого языка L как 'ji(L) = cc(Kn L). Подведя итог всему сказанному, мы имеем следующий результат.
Формальные свойства грамматик
ISl
T е о р е м а 18. Для каждого регулярного языка R гомоморфизм deem бесконтекстный язык; для каждого бесконтекстного языка L существует такой регулярный язык R, что L—'b(R).
