В ряде случаев при обработке регулярного множества кроме распознания необходимо его преобразование в другое множество.
Такие действия может выполнять МП-транслятор, на выходе которого будет формироваться выходная цепочка.
МП-транслятор задается :
1.Конечным множеством входных символов (включая символ конца цепочки "-+").
2.Конечным множеством выходных символов.
3.Конечным множеством магазинных символов (включая маркер дна магазина - /).
4.Конечным множеством состояний.
5.Упpавляющей таблицей, котоpая каждой комбинации: входной символ, магазинный символ(верхний символ магазина), состояние ставит в соответствие действие с магазином, входным символом, состоянием и выходными символами.
6.Hачальной конфигурацией (начальное состояние и начальное содеpжимое магазина).
7.Множеством допускающих конфигураций (комбинаций - состояние МП-транслятора и верхний символ магазина в момент, когда приходит символ "конец цепочки").
Строение ячейки в таблице переходов МП-траслятора аналогичо ячейке МП-распознавателя, но добавляется еще четвертое поле, в
котором указываются выходные символы, выдаваемые на этом шаге навыход.
--- Операции с магазином
¦
---+-----¬
¦ Вт.О /¦
Состояния ----+ Выт./П+--- Операции над входом
¦Si / Д¦
+---/---+
¦ ¦
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===========¦=============¦===========¦=============-
Входная цепочка допущена и преобразована к заданному виду.