Задача 2. Распознаватель арифметических выражений

Определим данный АМП:

1) Множество входных символов: { x, +, *, (, ), ┤ }.

2) Множество магазинных символов: { A, B, Ñ }

3) Множество состояний: t, является также и начальным состоянием автомата.

4) Алгоритм работы автомата.

- Цепочка принимается, если при ее окончании всем левым скобкам нашлись правые, для всех арифметическим знаков нашлись соответствующие «x».

- Цепочка отвергается, если:

1. Количество правых скобок превысило количество левых.

2. Количество «x» превысило количество арифметических знаков более чем на единицу.

3. Входная цепочка прочитана до конца, а левым скобкам не нашлось пары.

4. Входная цепочка прочитана до конца, а некоторым арифметическим знакам не нашлось соответствующих «x».

Алгоритм работы:

- Если входная головка читает «(», то в магазин заталкивается А.

- Если входная головка читает «)», то из магазина выталкивается А.

- Если входная головка читает «+» или «*», то в магазин заталкивается В.

- Если входная головка читает «х», то из магазина выталкивается В.

- Цепочка принимается, если при достижении символа ┤ магазин пуст Ñ.

- Цепочка отвергается, если:

1. На входе остаются правые скобки «)» или «х», а магазин пуст Ñ.

2. При достижении символа ┤ в магазине остаются символы А или В.

Магазинные символы	Входные символы
+, *	х	(	)	┤
А	↓В, →	Отвергнуть	↓A, →	↑, →	Отвергнуть
В	↓В, →	↑, →	↑↓A↓В, →	Отвергнуть	Отвергнуть
Ñ	↓В, →	Отвергнуть	↓A, →	Отвергнуть	Допустить

5) В начальном состоянии магазин содержит (ВÑ).

Пример 1: х+х*(х+х)

Номер шага	Содержимое стека	Остаток вх. цепочки
	ÑВ	х+х*(х+х) ┤
	Ñ	+х*(х+х) ┤
	ÑВ	х*(х+х) ┤
	Ñ	*(х+х) ┤
	ÑВ	(х+х) ┤
	ÑAB	х+х) ┤
	ÑA	+х) ┤
	ÑAB	х) ┤
	ÑA	) ┤
	Ñ	┤

Пример 2: x+x*(+x)

Номер шага	Содержимое стека	Остаток вх. цепочки
	ÑВ	х+х*(+х) ┤
	Ñ	+х*(+х) ┤
	ÑВ	х*(+х) ┤
	Ñ	*(+х) ┤
	ÑВ	(+х) ┤
	ÑAB	+х) ┤
	ÑABB	х) ┤
	ÑAB	) ┤

Теорема: класс языков, допускаемых МП-автоматами как по заключительному состоянию так и по пустому магазину совпадает с классом контекстно-свободных (КС) языков.

Задать язык списков типа а;[a;a;a;] распознающим АМП.

Определим данный АМП:

1) Множество входных символов: { a,;, [, ], ┤ }.

2) Множество магазинных символов: { A, B, Ñ }

3) Множество состояний: t, является также и начальным состоянием автомата.

4) Алгоритм работы автомата.

- Цепочка принимается, если при ее окончании всем левым скобкам нашлись правые, для всех «a» нашлись соответствующие «;».

- Цепочка отвергается, если:

1. Количество правых скобок превысило количество левых.

2. Количество «;» превысило количество «a».

3. Входная цепочка прочитана до конца, а левым скобкам не нашлось пары.

4. Входная цепочка прочитана до конца, а для некоторых элементов «a» не нашлось символа конца «;».

Алгоритм работы:

- Если входная головка читает «(», то в магазин заталкивается А.

- Если входная головка читает «)», то из магазина выталкивается А.

- Если входная головка читает «а», то в магазин заталкивается В.

- Если входная головка читает «;», то из магазина выталкивается В.

- Цепочка принимается, если при достижении символа ┤ магазин пуст Ñ.

- Цепочка отвергается, если:

1. На входе остаются правые скобки «)» или «;», а магазин пуст Ñ.

2. При достижении символа ┤ в магазине остаются символы А или В.

5) В начальном состоянии магазин пуст (Ñ).

Магазинные символы	Входные символы
a	;	(	)	┤
А	↓В, →	Отвергнуть	↓A, →	↑, →	Отвергнуть
В	↓В, →	↑, →	Отвергнуть	Отвергнуть	Отвергнуть
Ñ	↓В, →	Отвергнуть	↓A, →	Отвергнуть	Допустить