2015-06-28
423
1 Стратегия работы МП –распознавателя следующая:
а) входная цепочка состоит из 1 и 0, число и соотношение между которыми не ограничено при этом нули могут приходить только по два.
б) начинает работу распознаватель при пустом магазине в состоянии S 1; приход 1 ничего не меняет, приход 0 – вталкивается в магазин В и состояние меняется на S 2
в) после прихода второго 0 из магазина выталкивается В, состояние S 2, перход к очередному входному символу, который может быть только 1;
г) в состоянии S 2 приход символа 1 меняет состояние на S1.
д) цепочку допустить и процесс закончить в состояниях S1 или S 2 при пустом магазине.
2 Строим управляющую таблицу МП – распознавателя в соответствии с п.1:
Управляющая таблица имеет вид:
| ––| | |||||||||
| S1 | Ñ | S2 | Вт. В | П | S1 | О | П | Доп | |
| –– | –– | ||||||||
| B | Е | Е | Отв | ||||||
| S2 | Ñ | Е | S1 | О | П | Доп | |||
| –– | |||||||||
| B | S2 | Выт. В | П | Е | Отв | ||||
| –– | |||||||||
3 Проверим работу МП–транслятора
Разберем с помощью построенного МП–распознавателя вариант правильной цепочки: 1100100
|
|
|
| Необработ.цепочка | Сост. | Действия с маг. | Содерж. магазина |
| 1100100 –| 100100–| 00100 –| 0100 –| 100 –| 00 –| 0 –| –| | S1 S1 S2 S2 S1 S2 S2 S2 | О О Вт В Выт В О Вт. В Выт. В Выт. В допустить | Ñ Ñ В Ñ Ñ Ñ В Ñ Ñ Ñ |
4 Выполним полное описание МП – транслятора:
Входной алфавит { 0, 1 –-| }
Алфавит магазинных символов { В, Ñ }
Множество состояний { S 1, S 2 }
Начальная конфигурация (S 1, Ñ)
Допускающие конфигурации (S 1, Ñ) (S 2, Ñ)
Управляющая таблица приведена выше.
Построение МП – трансляторов
Построить МП–транслятор для преобразования цепочек вида А в вид В
А={ 1 (n) 0 (2n) } è В= { 1 (3n) 2 (n)}.
