Конечные автоматы (стр. 8 )

Операция ЗАМЕНИТЬ используется, когда на верху магазина X, а на входе 0. За один шаг эта операция выталкивает из магазина ненужный верхний символ X, помещает на его место символ для запоминания вхождения 0, а затем помещает на верх магазина другой X, чтобы указать, что автомат по-прежнему в «фазе вталкивания».

В этом примере впервые используется операция ДЕРЖАТЬ. Она появляется при переходе, на котором X выталкивается из магазина и начинается «фаза выталкивания». Входной символ 1 удерживается, т. e. сдвига на входе не происходит, и эту единицу можно сопоставить с соответствующим магазинным символом.

Сравнивая рис. 5.7 с предыдущим автоматом, изображенным на рис. 5.6, мы видим, что новый автомат использует только два вида информации: входной символ и магазинный символ, тогда как предыдущему автомату был необходим обычный набор из трех видов информации. С другой стороны, в новом автомате операции с магазином сложнее.

В отличие от конечных автоматов здесь нет понятия единственного «приведенного МП-автомата» и соответственно труднее сделать выбор между конкурирующими МП-автоматами. Во время написания этой книги не было даже известно, существует ли алгоритм, который решает проблему, допускают ли два МП-распознавателя одно и то же множество (к моменту перехода это по прежнему неизвестно). Во всяком случае, на этом примере видно, что для одной и той же задачи можно построить несколько хороших МП-автоматов и даже есть возможность выбирать, какую информацию запоминать с помощью состояния, а какую хранить в магазине.

5.5. Перевод с помощью МП-автоматов

МП-автомат называется МП-транслятором, если при распознавании он порождает выходную цепочку. Чтобы автомат выдавал выходную цепочку, управляющее устройство может наряду с обычными операциями над состоянием, входом и магазином производить операцию на выходе. При отсутствии выходной операции предполагается, что на выход ничего не выдается. Если надо выдать цепочку AB, то в определении соответствующего МП-перехода мы пишем

ВЫДАТЬ (AB)

Чтобы посмотреть, как можно пользоваться операцией ВЫДАТЬ, рассмотрим задачу перевода произвольной цепочки из нулей и единиц в цепочку вида 1m0n, где n и т соответственно число единиц и нулей в данной цепочке. Например, цепочка будет переведена в , так как в цепочке четыре единицы и два нуля.

Один из способов такого перевода заключается в том, чтобы выдавать единицы сразу при их появлении на входе, а при появлении на входе нулей помещать их в магазин. Когда встречается концевой маркер, автомат выталкивает из магазина нули и выдает их на выход. Управляющая таблица для автомата с одним состоянием, реализующего этот способ, изображена на рис. 5.9.

( ) —|

 

A s   ВТОЛКНУТЬ (A) сдвиг	вытолкнуть сдвиг	ВЫТОЛКНУТЬ ДЕРЖАТЬ
ВТОЛКНУТЬ (А) сдвиг	ОТВЕРГНУТЬ	ДОПУСТИТЬ

Начальное содержимое магазина: V

Рис. 5.9.

Последовательность конфигураций этого автомата при обработке цепочки показана на рис. 5.10. Если переход вызывает операцию с выходом, мы помещаем эту операцию между конфигурацией, вызывающей переход, и конфигурацией, наступающей после перехода.

1:	s	—|
2:	s 0	—|
	ВЫДАТЬ (1)
3:	s 0	0 1 1 —|
4:	s 0 0	1 1 —|
	ВЫДАТЬ (1)
5:	s 0 0	1 —|
	ВЫДАТЬ (1)
6:	s 0 0	—|
	ВЫДАТЬ (0)
7:	s 0	—|
	ВЫДАТЬ (0)
8:	s	—|
9:	ДОПУСТИТЬ

Множество, распознаваемое в нашем примере,— это просто (0+1)*, т. e. множество всех цепочек. В данном случае магазин служит не для распознавания, а только для перевода. Нули вталкиваются в магазин только для того, чтобы позже автомат выдал их на выходе. В следующем примере магазин будет использован как для распознавания, так и для перевода.

Рассмотрим проблему распознавания множества

{w2wr} w принадлежит (0+1)*

и перевода каждой цепочки w2wr в цепочку 1m0n, где n

и т соответственно число единиц и нулей в цепочке w. Так, цепочка

0 1 0

Рис. 5.10

должна быть переведена в

Чтобы выполнить этот перевод, построим МП-автомат, работающий в двух фазах. Первая из них — фаза вталкивания — длится до тех пор, пока на входе не встретится 2.

0 1 2 —|

0 1 s

 

СОСТОЯНИЕ (ФАЗА1) ВТОЛКНУТЬ (0) сдвиг	состояние (фаза 1) ВТОЛКНУТЬ (1) ВЫДАТЬ (1) сдвиг	СОСТОЯНИЕ (ФАЗА2) СДВИГ	ОТВЕРГНУТЬ
СОСТОЯНИЕ (ФАЗА 1) ВТОЛКНУТЬ (0) СДВИГ	СОСТОЯНИЕ (ФАЗА 1) втолкнуть (1) ВЫДАТЬ (1) сдвиг	СОСТОЯНИЕ (ФАЗА2) СДВИГ	ОТВЕРГНУТЬ
СОСТОЯНИЕ (ФАЗА1) ВТОЛКНУТЬ (0) СДВИГ	СОСТОЯНИЕ (ФАЗА 1) ВТОЛКНУТЬ ВЫДАТЬ (1) сдвиг	СОСТОЯНИЕ (ФАЗА2) СДВИГ	ОТВЕРГНУТЬ

а

0 1 2 —|

0 1 s

СОСТОЯНИЕ (ФАЗА2) вытолкнуть ВЫДАТЬ (0) СДВИГ	ОТВЕРГНУТЬ	ОТВЕРГНУТЬ	ОТВЕРГНУТЬ
ОТВЕРГНУТЬ	состояние (фаза 2) вытолкнуть сдвиг	ОТВЕРГНУТЬ	ОТВЕРГНУТЬ
отвергнуть	ОТВЕРГНУТЬ	ОТВЕРГНУТЬ	ДОПУСТИТЬ

б

Начальное содержимое магазина: s

Рис. 5.11. (а) Таблица для начального состояния ФАЗА 1;

(б) Таблица для состояния ФАЗА 2.

Во время этой фазы при появлении на входе символов 0 и 1 они помещаются в магазин. Кроме того, при появлении на входе единицы она выдается на выход. Вторая фаза — фаза выталкивания — наступает после того, как встретился входной символ 2. Во время этой фазы входные символы сравниваются с магазинными символами, чтобы проверить, совпадают ли они. В результате мы убедимся, что цепочка

1:	s ФАЗА1	—|
2:	s 0 ФАЗА1	—|
3:	s 0 0 ФАЗА1	—|
	ВЫДАТЬ (1)
4:	s 0 0 1 ФАЗА1	—|
5:	s 0 0 1 ФАЗА2	1 0 1 —|
6:	s 0 0 ФАЗА2	0 1 —|
	ВЫДАТЬ (0)
7:	s 0 ФАЗА2	1 —|
8:	ОТВЕРГНУТЬ

Рис. 5.12.

после 2 действительно является обращением цепочки, предшествующей символу 2. При совпадении символов каждый встреченный нуль выдается на выход. Фаза МП-автомата запоминается с помощью состояния. Две управляющие таблицы, реализующие эту схему, изображены на рис. 5.11, где используются состояния ФАЗА1 и ФАЗА2.

На рис. 5.12 показана работа автомата, отвергающего входную цепочку Так как эта цепочка отвергается, мы говорим, что у нее нет перевода, даже если МП-автомат выдает что-то на выход до того, как обнаруживает входной символ 1, который не совпадает с соответствующим символом цепочки, предшествующей символу 2.

--<*!!!*>--

*Created and inspected by Stalin.*

--<*!!!*>--