Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
1: (а, So, о)-+(Slt а)
2: (Ь, So, о) (S1, Ь)
3: (а, S1, a)-+(Su а)
4: (а, Su b)-*(Slt а)
5: (Ь, S1, a) ^ (S1, Ь)
6: (ь Su b)-*(Su Ь)
7: (с, Su a)-+(Se, е)
8: {с, Su b)-+(s„ е) 148
Часть II. Некоторые замечательные классы языков
9: (a, Se, a)-+(Se, 0) сравнение второй половины входной це-10: (Ь, Se, Ь) —>¦ (Se, 0) почки (х) с записью на ленте M и стирание букв в случае совпадения; 11: (В, Se, 0)->(5о, 0) стирание маркера 0 на ленте М.
Пример вычисления. Пусть входная цепочка есть abacaba. Тогда последовательность конфигураций нашего автомата такова:
Заметим, что построенный нами МП-автомат является детерминированным: левые части команд попарно различны и не содержат е.
9.1.4. МП-автомат, определяющий «зеркальный» язык без центрального маркера
Рассмотрим теперь язык Ln:
Ln = [хх І хе= {а, ЬУ),
отличающийся от предыдущего только отсутствием центрального маркера (ср. упр. 7.2.6.2). Будем применять ту же самую процедуру обработки цепочек. Поскольку теперь нет маркера, отмечающего середину цепочки, а символы, как и прежде, читаются один за Глава IX. Автомати с магазинной памятью
149
другим в одном направлении и без возвратов, автомат должен быть недетерминированным1). Для каждой позиции необходимо предусмотреть переход в состояние стирания.
Если предъявленная цепочка является неправильной, то она не может быть допущена автоматом. Когда входная цепочка правильна, возможны два случая:
— если переход в состояние стирания произойдет точно в середине цепочки, эта цепочка будет допущена, т. е. ее правильность будет распознана;
— в противном случае автомат остановится или закончит чтение входной цепочки, не очистив рабочую ленту.
Мы предлагаем читателю самостоятельно выписать команды такого МП-автомата.
§ 9.2. АВТОМАТЫ, ПОРОЖДАЮЩИЕ ЯЗЫКИ
До сих пор мы рассматривали . некоторый реальный механизм (ленты и управляющее устройство) ;
.. множество команд вида
(Sm, X),
которое задает абстрактный МП-автомат.
Эти команды могут интерпретироваться с помощью указанного механизма, и в результате получается реальный автомат, способный обрабатывать предъявленные ему цепочки: он допускает цепочки, принадлежащие рассматриваемому языку, и отвергает все прочие.
Однако множество команд, образующее абстрактный автомат, можно интерпретировать и другим способом: так, чтобы оно определяло реальный автомат иной природы, порождающий цепочки того же самого языка.
Порождающий автомат обладает внутренними состояниями, подобными состояниям допускающего автомата (так что мы можем отождествить их); у него имеется такая же лента М, а также лента Е, однако на этой последней он не читает, а пишет.
Каждой команде допускающего автомата (at, Sh Ak)->{Sm, х) сопоставляется команда порождающего автомата
i?t, Ak)-+{au Sm, х)
(и обратно).
Содержательно команда порождающего автомата означает следующее.
') Это замечание не есть, разумеется, доказательство того, что данный язык не может быть допущен никаким детерминированным МП-автоматом. Однако ®тот факт может быть строго доказан (см., например, Диковский [1969]),— "рим. ред, 150
Часть II. Некоторые замечательные классы языков
Находясь в ситуации (Sj1Zlft), порождающий автомат пишет а,-иа ленте Е, затем переходит в состояние Sm и поступает с лентой M в точности так же, как допускающий автомат. Предполагается, что начальным состоянием порождающего автомата является S0 и что при этом самым левым символом на ленте M всегда является а.
Поведение порождающего автомата определяется лишь частью ситуации, определяющей поведение допускающего автомата, однако ясно, что всякому правильному вычислению допускающего автомата отвечает правильное вычисление порождающего и наоборот'). Порождающий автомат, построенный по допускающему, порождает тот язык, который допускается этим последним. Порождающий автомат выдает правильную цепочку всякий раз, когда, исходя из описанных выше начальных условий, он возвращается в состояние S0, причем в этот момент лента M пуста.
Пример. Рассмотрим построенный в п. 9.1.3 МП-автомат, допускающий язык Lm = {хсх}. Вот новая интерпретация команд этого автомата:
1 и 2: записать на лентах E и M один и тот же символ, перейти в состояние Si; 3, 4, 5 и 6: записать на лентах E и M один и тот же символ,
остаться в состоянии Si; 7 и 8: записать на ленте E центральный маркер и перейти в состояние Se;
9 и 10: записать на ленте E символ, прочитанный на ленте M, стереть на M этот символ и перейти к чтению следующего символа;
11: дойдя до начального символа а, стереть его, перейти
в состояние S0 и записать на ленте E пробел.
В качестве упражнения читатель может описать процесс порождения этим автоматом цепочки аЪасаЪа.
Порождающий автомат может не быть детерминированным даже тогда, когда соответствующий ему допускающий автомат обладает этим свойством. Именно так обстоит дело в только что рассмотренном примере. «Сокращенные» ситуации вроде (Si, а), (S\, Ь) и т. п. допускают применение различных команд, и эта свобода выбора позволяет автомату строить первую половину цепочки как бы наугад; на второй половине цепочки поведение автомата становится детерминированным.
