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

Рассмотрим задачу проверки корректности вложенности круглых скобок.

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

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

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

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

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

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

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

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

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

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

2. Входная цепочка прочитана до конца, а левым скобкам не нашлось пары, т.е. при достижении символа ┤ в магазине остаются символы А.

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

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

Пример 1: (() ())

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

Пример 2: ()))

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