Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Для описания функционирования МП-автомата нам понадобятся следующие понятия:
1) Функция Я(ф), определенная на Vm следующим образом:
Ma)=- 1, Me) = о,
Мф) = |ф|, если ф<=Ум.
2) Физическая ситуация автомата — это тройка
Wt, Sh Ak),
где flj — символ, записанный на ленте E и обозреваемый входной головкой, Sj — состояние автомата и Ah — символ, записанный на ленте M и обозреваемый рабочей головкой.
3) Ситуация автомата — это либо физическая ситуация автомата, либо тройка, полученная из некоторой физической ситуации замещением символа Oi или Ak (или обоих) символом е. Именно здесь проявляется недетерминированный характер МП-автомата: в некоторой данной физической ситуации автомат может «закрыть-» тот «глаз», которым он обозревал аг-, или тот, которым он обозревал Ah\ тогда он «видит» этим «глазом» единичный символ.
Если автомат находится в физической ситуации {a,, S,, Ah), то он одновременно находится в следующих четырех ситуациях:
2, = (а„ Sh Ak),
52 = (e, Sh Ak),
53 = (аІ, Sh е),
Z4 = (в, Sh е).
4) Команда — это выражение вида
S (Sm, х),
где S — ситуация, Sm—состояние, а х обозначает либо е, либо а, либо цепочку в словаре Vm-
5) Абстрактным МП-автоматом называется конечное множество команд вида
^i-MSmf, X1);
поскольку рассматриваемые автоматы не являются детерминированными, возможны команды с совпадающими левыми частями (т. е. с одинаковыми ситуациями).
Теперь мы можем уточнить, что понимается под процессом вычисления.
Процесс вычисления. Вычисление в МП-автомате задается цепочкой в словаре Vs, записанной на входной ленте и 146
Часть II. Некоторые замечательные классы языков
ограниченной с обеих сторон пробелами:
aU
ah
Перед началом вычислений управляющее устройство находится в начальном состоянии So, а входная головка обозревает первый (самый левый) символ данной входной цепочки, при этом в первой (самой левой) ячейке рабочей ленты должен быть записан символ о, и эта ячейка должна обозреваться рабочей головкой.
Итак, вычисление начинается с физической ситуации (а{ , S0, о) и протекает следующим образом.
Предположим, что МП-автомат попал на каком-то шаге вычисления в ситуацию 2.
Если в программе автомата нет команды, применимой к 2, то автомат останавливается.
Если такая команда или несколько таких команд имеется, то автомат выбирает из них какую-то одну. Пусть выбрана команда 2 —> (Sm, х) ¦
В соответствии с этой командой происходит следующее: . управляющее устройство переходит в состояние Sm; .. если первый символ данной ситуации есть е, то входная головка оставляет ленту E неподвижной, а если первый символ — а;, то головка передвигает ленту так, чтобы обозревать символ, ближайший справа к йі\
... в зависимости от того, какое значение принимает х, рабочая головка оперирует с лентой M следующим образом:
Я (а) = — 1
Сдвинуть ленту на одну ячейку вправо, чтобы установить головку против символа, расположенного непосредственно слева от предыдущего символа; стереть предыдущий символ.
Я (е) = О
Не передвигать ленту; ничего не писать.
Я (ф) «= m
Записать последовательность * = ф справа от последнего символа; передвинуть ленту на гп ячеек влево так, чтобы головка обозревала самый правый из записанных символов. Глава IX. Автомати с магазинной памятью
147
Автомат, допускающий язык. Будем говорить, что некоторая цепочка во входном словаре допущена автоматом, если вычисление, начинающееся с этой цепочки, оканчивается ситуацией
(В, S0, В).
Цепочка называется допустимой, если существует вычисление, начинающееся с этой цепочки и заканчивающееся ситуацией (В, So, В). Поскольку рассматриваются недетерминированные МП-аитоматы, допустимая цепочка может не быть допущена в процессе того или иного конкретного вычисления.
Множество цепочек, допускаемых данным автоматом, представляет собой некоторый язык; говорят, что автомат допускает (или определяет) этот язык.
Ниже мы изучим класс языков, определяемых классом МП-автоматов; однако сначала приведем два примера.
9.1.3. МП-автомат, определяющий язык Lm
Пусть имеется язык
Lm = {хсх І хє{а, b}"}.
Спрашивается, можно ли построить МП-автомат, определяющий (допускающий) язык Lm.
Наличие центрального маркера с облегчает нашу задачу. Оказывается достаточным копировать заданную цепочку (т. е. переписывать ее на рабочую ленту) до тех пор, пока не появится маркер с. Начиная с этого момента, следует читать копию цепочки х в обратном направлении, сравнивая ее буква за буквой с цепочкой, претендующей на роль х. Если сравнение оказалось удачным, соответствующая буква стирается. Если предъявленная цепочка правильна, то рабочая лента M в конце концов окажется пустой; в противном случае, когда на M или на E еще остаются некоторые символы, автомат останавливается.
Таким образом, необходимо предусмотреть начальное состояние S0, состояние чтения Si и состояние стирания Se.
Искомый МП-автомат определяется следующими командами:
первая буква входной цепочки переносится на рабочую ленту M и автомат переходит в состояние Si (состояние чтения); буквы входной цепочки одна за другой переносятся на рабочую ленту М, причем автомат остается в состоянии Si; когда подцепочка х входной цепочки прочтена, лента M содержит х\ прочитав центральный маркер с, автомат переходит в состояние Se (состояние стирания); с рабочей лентой M ничего не происходит;
