Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Состояния M' будут обозначаться теми же символами, что и со-
1J Результаты этого раздела н разд. 4.2 получены во время совместной работы с М. П. Шюценберже. Краткое изложение см. [11 ]. Обобщения и относящиеся к ним результаты см. в работах [64, 65, 67].
Формальные свойства грамматик
ответствующие состояния М, и S0 снова будет начальным состоянием.
Предположим, что К и /С'— конфигурации машины-ленты для MnM' соответственно, удовлетворяющие следующим условиям: К достижимо из начальной конфигурации М. Цепочка ш, содержащаяся на ленте памяти устройства М’ в /С', сводится к цепочке у, содержащейся на ленте памяти устройства M в К. Кроме того, если уфе, то W=ZOt, для некоторого k (т.е. она имеет нештриховаи-ный символ на правом конце). Устройства MaM' наблюдают одну и ту же клетку идентичных входных лент и находятся в одном и том же внутреннем состоянии. В этом случае мы говорим, ЧТО к и К' согласованы. Заметим, что когда К и /С' согласованы, тогда либо M закончило работу с пустой лентой памяти в (этом случае содержимое ленты памяти M' есть гак ', которое сводится к е), либо M її M' находятся в одной и той же ситуации.
Правила в M' определяются правилами в M следующим способом. Пусть
(b, S1, а„) -> (Sj, х) (6)
есть правило в Al. Если хфа, то M' также имеет правило (6). Предположим, что х=а. Тогда, если а*—о (в этом случае /=0), то M' будет иметь правило (7), а если ак —о, то M' будет иметь правило (8) для каждого г (1 -<г<(7);
(Ь, S1, о)-+(S01 о'), (7)
(Ь, Si, ak)-±(Sj, a'ka'rar). (8)
Предположим теперь, что Ki и /C2- конфигурации М, а /Cl'— конфигурация M', которая согласована с K1- Конфигурация Ki ие является заключительной, и правило (6) в M переводит его из конфигурации Ki в /C2. Ясно, что если хфъ в правиле (6), то правило в M', соответствующее (6), будет переводить M' из К\ в конфигурацию /C2', которая согласована с /C2-
Предположим теперь, что х=о в правиле (6). Так как Ki по предположению не является заключительной конфигурацией, то M в Ki должно содержать на ленте памяти цепочку уак для некоторого k. Либо у—е, либо у~zar для некоторого г.
Предположим, что у~е. Тогда должно быть Ok=о н /=O в правиле (6). Следовательно, M' имеет соответствующее правило (7), которое переводит его из Ki в конфигурацию Ki'¦ Н° Ki согласована с Ku и> таким образом, содержимое ленты памяти M' в Ki должно быть to, где t сводится к е. Применением правила (7) M' переводится в К\, где содержимое ленты памяти равно Ли', которое сводится к е. Следовательно, Кг согласуется с /C2.
Предположим, что y=zar. Тогда правило (6) переводит M в
10 Заказ Л"° 563
ISO
H. Хомский
Ki, в котором леита памяти содержит гаг. Так как K1 согласована с K1, т0 содержимое ленты памяти M' в K1' должно равняться цепочке tar uak, где t сводится к г, а и к г. По построению M' имеет правило (8), соответствующее правилу (6); оно переводит M' в Kt', которое идентично Ki в отношении входной ленты и внутреннего состояния и в котором лента памяти содержит tar uak' a/ar, что сводится к гаг=у и Кг согласована с Ki .
В каждом случае мы видим, что если правило (6) переводит M из K1 в Ki, то M1 имеет правила, переводящие его из K11 (согласованной с K1) в Ki (согласованную с Ki).
Предположим, что K1— снова конфигурация М, не являющаяся заключительной, K11— согласованная конфигурация М, что правило /' в M' переводит Al' в конфигурацию K2 и что нет правила в М, переводящего его в конфигурацию Ki, которая согласована с Ki- Ясно, что /' не было выведено (с помощью ранее данной конструкции) из некоторого правила М, имеющего такой же вид, как правило (6), где x=j=s. Таким образом, мы можем предположить, что / есть правило вида (7) или (S) и что Г было получено описанным способом из правила /: (b, S1, ak)-+(S/, о). В любом случае, так как K1 и K1 согласованы и ни одно из них не является заключительной конфигурацией, лента памяти M ъ K1 должна содержать цепочку уа„, где у=е или y~zas для некоторого s, и лента памяти M' в K1 должна содержать цепочку vak, где v сводится к у.
Предположим, что Г— правило (7). Тогда ак=а и содержимое ленты памяти M1 в Ki есть изо'. Устройство M' заканчивает работу в состоянии S0 с лентой памяти, содержащей цепочку, которая сводится к у; но так как °(=ак) не может быть напечатана на ленте памяти ни на каком шаге M и так как содержимое ленты памяти M в K1 есть ус, обязательно у—е. Итак, / переводит M из K1 в конфигурацию Ki, которая согласуется с Ki' вопреки предположению.
Остается предположить, что Г есть правило (8). Тогда содержание ленты памяти M' в Ki есть vaka'k CLi си, что сводится к yaka'ka'rar и в свою очередь к уа/аг. Если у—е, то лента памяти M' блокирована в Ki- Предположим, что y = zas. Тогда I переводит M в конфигурацию Ki, в которой лента памяти содержит zas. Предположим, что s=r. Тогда содержание ленты памяти M1 в Ki', которое сводится к ya/ar=zafl‘ гаг, сводится далее к zar=zas. Ho в этом случае Кг и Ki согласованы вопреки предположению. .Следовательно, гфз. Ho в этом случае лента памяти M' B-Ki' снова блокирована. Следовательно, в любом случае, если /' есть правило (8), она блокирована.
