Р е ш е н и е

Разработаем логическую последовательность действий (алгоритм работы) МП –автомата для распознания заданного по условию множества цепочек:

1 При обработке правильной цепочки первыми символами, которые нужно обработать МП –автомату, будет серия из n "0". Их количество нужно запомнить для сравнения с количеством "1".

2 Поступление каждого символа "0" будем сопровождать вталкиванием в магазин магазинного символа А для того, чтобы запомнить количество нулей и сравнить потом с количеством единиц (в начальном состоянии магазин пуст).

3 После прихода первого символа "1", нули не должны поступать (поступление "0" должно переводить автомат в состояние ошибки " Е ").

4 Поступление каждого символа "1" должно сопровождаться выталкиванием из магазина символа А. Таким образом будет контролироваться равенство количества "0" и "1".Цепочка будет допускаться МП –автоматом, если при поступлении символа"–|" магазин окажется пустым.

Реализуем описанную стратегию в конкретном МП –автомате:

1 Множество входных символов V = {0,1,–|}.

2 Множество магазинных символов {#,А}.

3 Множество состояний S = {s1, s2}.

4 Hачальная конфигурация МП –автомата – состояние s1, магазин пуст(верхний символ магазина #).

5 Допускающая конфигурация МП –автомата – состояние s2, магазин пуст(верхний символ магазина #).

6 Таблица переходов имеет вид представленный на рисунке(см. след. стр.):

Проверим правильность работы построенного МП –автомата.. Для этого разберем цепочку 0011–|, которая должна быть допущена. Результаты пошагового выполнения действий сведены в таблицу.

Необработанная цепочка	Состояние автомата	Действия с магазином	Содержимое магазина
0011–|	s1	–	#
011–|	s1	Вт. А	A#
11–|	s1	Вт. А	AA#
1–|	s2	Выт. А	A#
–|	s2	Выт. А	#

Цепочка допущена, т.к. конечная конфигурация МП –автомата допускающая (состояние s2, в магазине пусто).

5.2 Автоматы–трансляторы с магазинной памятью

В ряде случаев при обработке регулярного множества кроме распознания необходимо его преобразование в другое множество. Такие действия может выполнять МП –транслятор, на выходе которого будет формироваться выходная цепочка.

МП – транслятор задается:

1 конечным множеством входных символов (включая символ конца цепочки "–|");

2 конечным множеством выходных символов;

3 конечным множеством магазинных символов (включая маркер дна магазина – #);

4 конечным множеством состояний;

5 управляющей таблицей, которая каждой комбинации трех параметров: входной символ, магазинный символ(верхний символ магазина), состояние – ставит в соответствие четыре параметра (действие с магазином, входным символом, состоянием и выходными символами);

6 начальной конфигурацией (начальное состояние и начальное содержимое магазина);

7 множеством допускающих конфигураций (комбинаций – состояние МП –транслятора и верхний символ магазина в момент, когда приходит символ "конец цепочки").

Строение ячейки в таблице переходов МП –транслятора (см. рисунок) аналогично строению ячейки МП –распознавателя, в которую добавлено внизу четвертое поле (в нем указываются выходные символы, выдаваемые на этом шаге на выходе МП –транслятора).

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

Пример: Построить МП –транслятор для распознания множества {W 2 V} и преобразования его в множество {1(n) 0(m)}, где W – произвольная цепочка из " 0 " и " 1 ", V -цепочка обратная W, m – число " 0 " до символа " 2 ", n – число " 1 " до символа " 2 " (конкретный пример цепочки и ее преобразования 0010112110100 à 111000).