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

В ряде случаев при обработке регулярного множества кроме распознания необходимо его преобразование в другое множество.

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

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

1.Конечным множеством входных символов (включая символ конца цепочки "-+").

2.Конечным множеством выходных символов.

3.Конечным множеством магазинных символов (включая маркер дна магазина - \/).

4.Конечным множеством состояний.

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

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

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

Строение ячейки в таблице переходов МП-траслятора аналогичо ячейке МП-распознавателя, но добавляется еще четвертое поле, в

котором указываются выходные символы, выдаваемые на этом шаге навыход.

--- Операции с магазином

¦

---+-----

¦\ Вт.О /¦

Состояния ----+ \Выт./П+--- Операции над входом

¦Si\0 / Д¦

+---\/---+

¦ ¦

L------T--

¦

L- Выход (символы на выходе)

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

цепочка отвергается.

Пример

Распознать множество {W 2 V} и преобразовать его в множество

{1(n) 0(m)}, где W-цепочка из "0" и "1",V-цепочка обратная W, m

- число "0" до "2", n - число "1" до "2".

Конкретный пример 0010112110100 ==> 111000

Решение

Опишем работу транслятора

Для работы МП-транслятора необходимо запоминать не только количество единиц и нулей цепочки W, но и их порядок для проверки цепочки V. Это можно реализовать, вталкивая в магазин символ В при приходе единицы и символ А при приходе нуля до момента прихода двойки (т.е. до момента окончания цепочки W);таким образом в магазине окажется копия цепочки W, но записанная в обратном порядке (верхним в магазине будет символ, пришедший последним).

При этом на выход при поступлении "1" нужно выдать тоже "1", а при поступлении "0" на выход не выдавать символов. Приход двойки нужно зафиксировать сменой состояния транслятора. Во втором состоянии действия транслятора следующие:

а) верхний символ в магазине В и пришла единица - вытолкнуть В, на выход ничего не выдавать и перейти к обработке следующего символа входной цепочки;

б) верхний символ в магазине А и пришел ноль - вытолкнуть А, на выход выдать "0" и перейти к обработке следующего символа входной цепочки;

в) оставшиеся два варианта - состояние ошибки Е (входная цепочка не соответствует виду {W 2 V}.

Зададим МП-транслятор:

1. Управляющая таблица

є 0 і 1 і 2 і Дґ є

г======T======+---------+---------+---------+---------¦

¦ ¦ ¦ \Вт. А /¦ \ Вт.В /¦ ¦ ¦

¦ ¦ ¦ \ / ¦ \ / ¦ ¦ ¦

¦ ¦ \/ ¦ S1\ / П¦ S1\ / П¦ Е ¦ Отв. ¦

¦ ¦ +----\/---+----\/---+ ¦ ¦

¦ ¦ ¦ --- ¦ 1 ¦ ¦ ¦

¦ +------+---------+---------+---------+---------¦

¦ ¦ ¦ \Вт. А /¦ \ Вт.В /¦ \ 0 /¦ ¦

¦ ¦ ¦ \ / ¦ \ / ¦ \ / ¦ ¦

¦ S1 ¦ A ¦ S1\ / П¦ S1\ / П¦ S2\ / П¦ Отв. ¦

¦ ¦ +----\/---+----\/---+----\/---+ ¦

¦ ¦ ¦ --- ¦ 1 ¦ -- ¦ ¦

¦ +------+---------+---------+---------+---------¦

¦ ¦ ¦ \Вт. А /¦ \ Вт.В /¦ \ /¦ ¦

¦ ¦ ¦ \ / ¦ \ / ¦ \ 0 / ¦ ¦

¦ ¦ B ¦ S1\ / П¦S1 \ / П¦ S2\ / П¦ ¦

¦ ¦ +----\/---+----\/---+----\/---+ Отв. ¦

¦ ¦ ¦ --- ¦ 1 ¦ --- ¦ ¦

¦------+------+---------+---------+---------+---------¦

¦ ¦ \/ ¦ Е ¦ Е ¦ Е ¦ Доп. ¦

¦ +------+---------+---------+---------+---------¦

¦ ¦ ¦ \Выт.А /¦ ¦ ¦ ¦

¦ ¦ ¦ \ / ¦ Е ¦ Е ¦ ¦

¦ S2 ¦ A ¦ S2\ / П¦ ¦ ¦ ¦

¦ ¦ +----\/---+ ¦ ¦ Отв. ¦

¦ ¦ ¦ 0 ¦ ¦ ¦ ¦

¦ +------+---------+---------+---------+---------¦

¦ ¦ ¦ ¦ \ Выт.В/¦ ¦ ¦

¦ ¦ ¦ ¦ \ / ¦ ¦ ¦

¦ ¦ B ¦ Е ¦ S2\ / П¦ E ¦ ¦

¦ ¦ ¦ +----\/---+ ¦ Отв. ¦

¦ ¦ ¦ ¦ --- ¦ ¦ ¦

L======¦======¦=========¦=========¦=========¦=========-

- 10 -

2. Множество состояний {S1,S2}.

3. Множество входных символов:{0,1,2,-+};

4. Множество магазинных символов:{А,В,\/};

5. Множество выходных символов:{0,1};

Для примера разберем цепочку 0112110:

г===========T=============T===========T=============

¦ Цепочка ¦ Состояние ¦ Магазин ¦ Выход ¦

¦-----------+-------------+-----------+-------------¦

¦ 0112110-+ ¦ S1 ¦ \/ ¦ --- ¦

¦ ¦ ¦ ¦ ¦

¦ 112110-+ ¦ S1 ¦ А \/ ¦ --- ¦

¦ ¦ ¦ ¦ ¦

¦ 12110-+ ¦ S1 ¦ ВА \/ ¦ 1 ¦

¦ ¦ ¦ ¦ ¦

¦ 2110-+ ¦ S1 ¦ ВВА\/ ¦ 11 ¦

¦ ¦ ¦ ¦ ¦

¦ 110-+ ¦ S2 ¦ ВВА\/ ¦ 11 ¦

¦ ¦ ¦ ¦ ¦

¦ 10-+ ¦ S2 ¦ ВА\/ ¦ 11 ¦

¦ ¦ ¦ ¦ ¦

¦ 0-+ ¦ S2 ¦ А\/ ¦ 11 ¦

¦ ¦ ¦ ¦ ¦

¦ -+ ¦ S2 ¦ \/ ¦ 110 ¦

¦ ¦ ¦ ¦ ¦

L===========¦=============¦===========¦=============-

Входная цепочка допущена и преобразована к заданному виду.