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

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

1 В процессе разбора входной цепочки МП –транслятору необходимо запоминать не только количество единиц и нулей части цепочки W, но и порядок их следования для последующей проверки цепочки V. Запоминание можно реализовать, вталкивая в магазин символ В при приходе единицы и символ А – при приходе нуля. Этот процесс продолжать до прихода символа "2" (т.е. до момента окончания цепочки W); в результате таких действий в магазине окажется копия цепочки W, записанная в обратном порядке (верхним в магазине будет символ, соответствующий последнему символу в цепочке W).

2 При разборе W на выход при приходе " 1 " нужно выдавать тоже " 1 ", а при приходе " 0 " на выход не выдавать ничего. Приход " 2 " нужно зафиксировать сменой состояния транслятора; с магазином действий не выполнять.

3 Во втором состоянии идет обработка части цепочки V и действия транслятора следующие:

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

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

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

Параметры МП-транслятора:

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

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

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

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

5 Управляющая таблица МП –транслятора (приведена на рисунке).

Для проверки работы МП-транслятора разберем цепочку 0112110:

Выполнена трансляция входной цепочки (цепочка проверена и преобразована к заданному виду).

5.3 Задачи к главе 5

Задача 1 Для приведенных в таблице (см.ниже) вариантов множеств цепочек построить МП –распознаватели с полным описанием процесса построения.