Допускаемые операции с входными символами

1 Держать текущий входной символ обрабатываемой цепочки (Д).

2 Перейти к следующему символу обрабатываемой цепочки (П).

Примечание. Запрещен переход к следующему символу, если текущий символ –| ("конец цепочки").

Допускаемые операции над магазином

Магазин можно представить в виде одностороннего стека или упорядоченного списка, в котором доступен для выполнения действий только первый(верхний) символ. При вталкивании нового символа в магазин все, находящиеся до этого в магазине символы, смещаются на одну позицию (для определенности вправо). Доступ возможен только к верхнему символу магазина. С ним и выполняются операции, указанные в управляющей таблице:

1 Втолкнуть в магазин магазинный символ, к примеру А (Вт.А).

2 Вытолкнуть из магазина верхний символ, к примеру А (Выт.А).

3 Оставить магазин без изменений (О).

Примечания:

1 Запрещено выталкивание и выталкивание символа дна магазина # (в магазине этот символ один и всегда заканчивает цепочку магазинных символов).

2 Допускается выполнять вталкивание нескольких магазинных символов (Вт.АВ).

3 В ряде случаев допускается действие "заменить", т.е. верхний символ магазина заменяется некоторой указанной цепочкой (Зам. Аав) Для определенности при записи содержимого магазина будем полагать, что символ дна # занимает самое правое положение в списке. К примеру, содержимое магазина до выполнения операции " Зам. Аав " – ВВА#; после – АавВА#.

Результатом работы для МП – распознавателя будет сообщение "допустить" или "отвергнуть" цепочку, обработанную посимвольно после, поступления символа "конец цепочки" (если автомат попал в состояние ошибки, то цепочка отвергается до прихода символа "конец цепочки").

Входная цепочка допускается МП– распознавателем, если под воздействием этой цепочки автомат, начавший работу в начальной конфигурации (в начальном состоянии и с начальным содержимым магазина), находится в допускающей конфигурации после поступления символа "конец цепочки", иначе цепочка отвергается.

Пример: Построить МП –распознаватель для распознания множества цепочек следующего вида: { 0(n)1(n)| n>0} (правильная цепочка состоит из нулей, после которых следует такое же количество единиц).