Р Е Ш Е Н И Е

1 Стратегия работы МП – транслятора следующая для преобразования цепочек:

а) входная цепочка состоит в первой части из серии 1, количество которых необходимо запомнить для сравнения со второй частью (серия 0, которых должно быть 2n);

б) при приходе 1 – втолкнуть в магазин ВВ, состояние S₁, перейти к очередному входному символу, на выход выдать 111;

в) после прихода первого 0 – вытолкнуть В, поменять состояние на S₃, на выход ничего не выдаватьи перейти к очередному входному символу;

г) при приходе второго 0 – вытолкнуть из магазина В, поменять состояние на S₂, на выход выдать 2 и перейти к очередному входному символу; в состоянии S₂ повторить действия пункта в);

д) цепочку допустить и процесс закончить в состоянии S₂ при пустом магазине.

2 Строим управляющую таблицу МП – транслятора:

Управляющая таблица имеет вид:

			––|
S1	Ñ	S1	Вт. ВВ	П	Е	Отв
	B	S1	Вт. ВВ	П	S3	Выт. В	П	Отв
	––
S2	Ñ	Е	Е	Доп
	B	Е	S3	Выт. В	П	Отв
––
S3	Ñ	Е	Е	Отв
	B	Е	S2	Выт. В	П	Отв

3 Проверим работу МП–транслятора

Разберем с помощью построенного МП–транслятора цепочку:

110000 –-| è 11111122

Необработ.цепочка	Сост.	Действия с маг.	Содерж. магазина	Цепочка на выходе
110000 –| 10000 –| 0000 –| 000 –| 00 –| 0 –| –|	S1 S1 S3 S2 S3 S2	Вт. ВВ Вт. ВВ Выт. В Выт. В Выт. В Выт. В допустить	Ñ ВВ Ñ ВВВВ Ñ ВВВ Ñ ВВ Ñ В Ñ Ñ	–

4 Выполним полное описание МП–транслятора

Входной алфавит { 0, 1 –-| }

Алфавит магазинных символов { В, Ñ }

Выходной алфавит { 1, 2 }

Множество состояний { S₁, S₂, S₃ }

Начальная конфигурация (S_1, Ñ)

Допускающая конфигурация (S_2, Ñ)

Управляющая таблица приведена выше.

Варианты заданий для самостоятельной подготовки

Задание 1

Построить МП–распознаватель для распознания бинарных цепочек вида:

{0(n) 1(2n) 0(2m) 1(m)}.

Задание 2

Построить МП –транслятор для следующего преобразования бинарных цепочек: { 1(2n) 0(m)} è { 0(n) 1(2n+m)}.

Задание3

Построить МП–распознаватель для распознания бинарных цепочек вида:

{0(n) 1(2m) 0(m)1(3n)}.

Задание 4

Построить МП –транслятор для следующего преобразования бинарных цепочек: {1(n+1) 0(m)} è {0(n) 1(3m)}.

Задание 5

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

Задание 6

Построить МП –транслятор для следующего преобразования бинарных цепочек: {1(n) 0(m)} è {0(n) 1(2n+m+1)}.

Задание 7

Построить МП–распознаватель для распознания бинарных цепочек вида:

{a(2n) b(m) a(n + 2m+1)}.

Задание 8

Построить МП –транслятор для следующего преобразования цепочек:

{a(n) b(m) a(n) } è { 0(3n) 1(2m+n)}.

Задание 9

Построить МП –распознаватель для распознания бинарных цепочек из 0 и 1, где 0 встречается только по два, а 1 по три.