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

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

Примечания:

1 В заданиях для входных цепочек используется двухсимвольный алфавит V={0,1} или V={a,b}; в круглых скобках после символа алфавита указано, сколько раз подряд он должен повториться в правильной цепочке (степень символа).

2 Для МП –транслятора приведены входная и выходная цепочки.

3 Значения m,n,k = 1,2,3...

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

(см. соответствующий раздел лекций по ДМ)

1 Назначение и принципы работы автоматов с магазинной памятью (МП –автоматов).

2 Устройство и функционирование магазина МП –автомата.

3 Построение управляющей таблицы для МП –автомата и ее назначение.

4 Последовательность построения МП –автомата для распознания регулярных цепочек.

5 МП–транслятор, его назначение; отличие от МП–распознавателя.

Тема № 3 Формальные языки и грамматики

Построение МП – распознавателей для КС–грамматик

ЗАДАНИЕ

Для заданной грамматики G[S] выполнить эквивалентные преобразования правил (исключить недостижимые и непродуктивные символы, при необходимости – устранить левостороннюю рекурсию). Определить тип полученной грамматики и построить автомат для ее распознания (КА – или МП –распознаватель); реализовать автомат–распознаватель и проверить его работу.

G[S] = (VT = {a,b}; VN = {S,A,B,C,D}; P={ SèaAb(1); SèbS(2); AèbaB(3); AèaC(4); Dèb(5); Bèb(6)}).