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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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