Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Предположим теперь, что я=1. Тогда либо L(G) конечен (и регулярен), либо G сильно связна и порождает регулярный язык, как только что было показано.
Допустим, что утверждение (58) верно для всех грамматик, содержащих менее чем п нетерминальных символов. Предположим, что A1 есть начальный символ в G, которая имеет нетерминальные символы All-^lAa. Мы можем допустить, что G не содержит лишних символов и не является сильно связной. Таким образом, для некоторого / не существует <f, таких, что Aj-MfA1lI/. Предположим, что }Н=\. Образуем G' вычеркиванием из G каждого правила Aj-^f и заменой Aj во всех правилах на новый символ а. По индуктивному предположению язык L', порождаемый грамматикой G', является регулярным, так же как и множество K—\x\Aj-*x\. Очевидно, что если L1 и L1 регулярны и L3 состоит из всех цепочек, образованных из х ? L1 заменой каждого символа а (если он встречается) в х некоторой цепочкой из L2, тогда La— регулярный язык. L(G) построен таким сп'особом из L' и /( и в силу этого регулярен.
Предположим, ЧТО 1=1. Пусть <fr — такие цепочки, что
A1-Xfi. Пусть Ki для каждого і. Предположим,
что Ti=Ot1 ... ат. По индуктивному предположению множество Lj= [хIa ^xj регулярно. Из теоремы 2 следует, что Ki, а следовательно и L, также регулярно. Этим доказано утверждение (58). Кроме того, утверждение непосредственно следует из более сильного результата, который будет получен ниже.
Мы исследовали так подробно только вопрос слабой эквивалентности грамматик, т. е. вопрос о том, порождают лн они один и тот же язык. Мы определили также понятие сильной эквивалентности двух грамматик, которые не только порождают один и тот же язык, HO также одно и то же множество структурных описаний (см. разд. 5.1 предыдущей главы). О сильной эквивалентности известно мало, однако важно отметить, что мы можем расширить утверждение (58) таким образом, что если задана грамматика без самовставления G1 то мы можем построить конечный преобразователь Т, такой, что он, в том смысле как это будет уточнено, сильно эквивалентен G. Мы можем также усилить этот результат до любой конечной степени самовставляемости. К отдельным следствиям из этих положений мы вернемся в следующей главе (см. также работу [10]).
15*
204
H. Хомский
Для уточнения сказанного рассмотрим более подробно класс конечных преобразователей. Мы можем предположить, что входной алфавит каждого преобразователя T есть подмножество V т (фиксированного и универсального множества терминальных символов для всех бесконтекстных грамматик). Мы предполагаем, что выходной алфавит каждого преобразователя есть подмножество некоторого фиксированного множества Ao- Если задан Т, мы говорим, что T допускает х и ставит ему в соотве пствие структурное описание у [или коротко: T порождает (х, у)] только в том случае, когда T начинает работу в состоянии S0 с пустой лентой памяти, считывая самый левый символ цепочки на входной ленте, и заканчивает работу при первом возвращении в S0, считывая # на входной ленте, имея у в качестве содержимого ленты памяти1). Таким образом, если T порождает (х, у), то он допускает х как конечный автомат, не имеющий выхода (см. разд. 1.2), н преобразует его в у как преобразователь.
Чтобы сравнить порождающую способность преобразователей, понимаемых таким образом, с порождающей способностью бесконтекстных грамматик, допустим, что нам задано эффективное взаимно однозначної соответствие Ф, отображающее множество структурных описаний, порождаемых бесконтекстными грамматиками (задаваемых, скажем, цепочками с системами отмеченных скобок, см. стр. 170) в множество цепочек в Ao - Мы можем теперь определить строгую эквивалентность как отношение между бесконтекстными грамматиками и конечными преобразователями. '
Определение 9. Если задана бесконтекстная грамматика G и конечный преобразователь Т, mo G и T сильно эквивалентны тогда и только тогда, когда выполнено следующее условие'. T порождает (х,Ф[у)) в том и только в том случае, когда G порождает х со структурным описанием у.
Таким образом, если T строго эквивалентно G, то T допускает только цепочки, порождаемые G, и преобразует каждую такую цепочку в каждое структурное описание, сопоставленное ей грамматикой G, и ни во что другое.
Мы можем теперь дать точную формулировку обобщения утверждения (58).
Теорема 34. Существует эффективная процедура W1 такая, что если задана нормальная бесконтекстная грамматика без самовставления G, то V(G) есть конечный преобразователь, сильно эквивалентный G [8].
*) Более точно, в соответствии с описанием преобразователей, данным в разд. 1.5, мы будем говорить, что T начинает работу, наблюдая а на (в остальном) пустой лейте памяти, и заканчивает работу с ау в качестве содержимого ленты памяти.
Формальные свойства грамматик
205
Как было ранее отмечено, эта процедура легко может быть обобщена на случай любой конечной степени самовставляемости способом, который мы опишем более тщательно. Очевидно, что утверждение (58) и теорема 33 следуют из теоремы 34.
