Р Е Ш Е Н И Е

1 Проверим нетерминальные символы грамматики на достижимость и продуктивность:

В исходной грамматике правила пронумерованы для ссылок.

G[S] = (VT = {a, b}; VN = { S, A, B, C, D }; P = { S è aAb;(1) S è bS;(2)

A è baBb;(3) A è bC (4); D è b; (5) B è b;(6) })

а) проверка достижимость:

(1) (3) (указаны номера правил)

S è A è B ( нетерминал D недостижим и не нарушая эквивалентности

\ è С

из исходной грамматики удаляем правила (5);

б) проверка оставшихся нетерминалов на продуктивность:

В соответствии с правилом (6) продуктивен нетерминал B; в соответствии с правилом (3) продуктивен нетерминал A; в соответствии с правилом (1) продуктивен нетерминал Z; нетерминал С непродуктивен (правило (4) убираем в исходной грамматике).

После эквивалентных преобразований новая грамматика имеет вид:

G[S₁] = (VT = {a, b}; VN = { S, A, B }; P = { S è aAb;(1) S è bS;(2)

A è baB (3); B è b;(4) })

2 Определим тип полученной грамматики: по виду правил можно сказать, что это КС-грамматика (неправосторонняя – несоответствие в правиле (1)).

Полученная грамматика является S-грамматикой – (по определению)

Для такой грамматики множества “Выбор” для правил с одинаковыми левыми частями попарно не пересекаются (пересечение пусто). “Выбор S( 1 ) ” = { a }; “Выбор S( 2 ) ” = b

“Выбор S( 1 ) ” Ç “Выбор S (2)” = { (пусто) }.

Вывод: исследуемая грамматика является S – грамматикой, для которой известен алгоритм построения МП–распознавателя.

3 Построим МП–распознаватель с одним состоянием.

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

	a	b	––|
Ñ	E	E	Доп.
S	Зам. Ab	П	Зам. S	П	Отв.
A	E	Зам. aB	П	Отв.
B	E	Выт. B	П	Отв.
a	Выт. a	П	Е	Отв.
b	Е	Выт. b	П	Отв.

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

(2) (1) (3) (4) <– номера правил

S Þ b S Þ b a A b Þ b a b a B b Þ b a b a b b

Необработ. цепочка	Обраб. симв.	Верхн. маг. симв	Содерж. магазина	Действия с маг.
bababb –-| ababb –-| babb –-| abb –-| bb–-| b–-| –-|	b a b a b b –-|	S S A a B b Ñ	S Ñ S Ñ A b Ñ aB b Ñ B b Ñ B Ñ Ñ	О Зам. Ab Зам. aB Выт. a Выт. B Выт. b Доп.

5 Выполним полное описание МП – распознавателя:

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

Алфавит магазинных символов {S, A, B, a, b, Ñ}

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

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

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

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

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

№ задания	Грамматика
	G[S] = (VT = {a, b}; VN = { S, A, B, C, D }; P = { S è abAa; S è bS; A è baB; A è aCb; D è a; B è b })
	G[Z] = (VT = {a, b}; VN = { Z, A, B, C }; P = { Z è abA; Z è baZ; A è abAb; A è bB; A è e; C è abZa; C è e}) (e –пустая цепочка)
	G[S] = (VT = {a, b}; VN = { S, A, B, C, D }; P = { S è aAb; S è bS; A è baB; A è aC; D è b; B è b })
	G[S] = (VT = {a, b}; VN = { S, A, B, C, D }; P = { S è abA; S è bS; A è baBa; A è aC; D è aC; B è b })
	G[Z] = (VT = {a, b}; VN = { Z, A, B, C }; P = { Z è abA; Z è bZ; A è aAb; A è bB; A è e; C è aZB; C è b}) (e –пустая цепочка)
	G[Z] = (VT = {a, b}; VN = { Z, A, B, C }; P = { Z è abA; Z è bZ; A è abAb; A è bB; A è e; C è aZa; C è e}) (e –пустая цепочка)
	G[Q] = (VT = {a, b}; VN = { Q, A, B }; P = { Q è abQ; Q è bA; A è abA; A è bB; B è bB; B è a })
	G[Z] = (VT = {a, b}; VN = { Z, A, B, C }; P = { Z è abA; Z è bZ; A è abAb; A è bB; A è e; C è aZB; C è b}) (e –пустая цепочка)