Далеко не для всех регулярных множеств можно построить КА-распознаватель, так как КА не имеет возможности сосчитать и запомнить количество символов обрабатываемой цепочки. Для этой цели используется специальное устройство - магазин, в который можно помещать символы или удалять их, запоминая или сравнивая количество символов входной цепочки. Такой автомат называется автоматом-распознавателем с магазинной памятью (сокращенно - МП-автоматом).
МП-автомат задается :
1.Конечным множеством входных символов (включая символ конца цепочки "-+").
2.Конечным множеством магазинных символов (включая маркер
дна магазина - /).
3.Конечным множеством состояний.
4.Упpавляющей таблицей, котоpая каждой комбинации: входной символ, магазинный символ(верхний символ магазина), состояние - ставит в соответствие действие с магазином, входным символом, и состоянием.
5.Hачальной конфигурацией (начальное состояние и начальное содеpжимое магазина).
6.Множеством допускающих конфигураций (комбинаций - состояние МП-автомата и верхний символ магазина в момент, когда приходит символ "конец цепочки").
Допускаемые операции над входом
1.Держать входной символ (Д).
2.Перейти к очередному символу (П).
Примечание: запрещено запрашивать входной символ после прихода
символа -+ ("конец цепочки").
Допускаемые операции над магазином
1.Втолкнуть в магазин магазинный символ, к примеру А (Вт.А).
2.Вытолкнуть из магазина верхний символ, к примеру А (Выт.А).
3.Оставить магазин без изменений (О).
Примечания: а) запрещено выталкивание символа дна магазина /;
б) допускается действие с несколькими символами
(верхним в магазине и следующих за ним);
в) в ряде случаев допускается действие "Заменить",
т.е. верхний символ магазина заменяется некоторой цепочкой. Например "Зам Аав" означает, что верхний символ магазина заменяется на цепочку Аав. Для определенности при записи содержимого магазина будем полагать, что символ дна / занимает самое левое положение. Магазин до операции "Зам Аав" ВВА/; после - АавВА/.
Результатом работы для МП-pаспознавателя будет сообщение"допустить" или "отвеpгнуть". Входная цепочка допускается МП-pаспознавателем , если под воздействием этой цепочки автомат, начавший pаботу в начальной конфигурации ( в начальном состоянии и с начальным содеpжимым магазина) приходит к допускающей конфигурации после поступления символа "конец цепочки", иначе цепочка отвеpгается.
Рассмотрим строение ячейки в таблице переходов МП-распознавателя.
--- Операции с магазином
¦
---+-----¬
¦ Вт. /¦
Состояния ----+ Выт./П+--- Операции над входом
¦Si / Д¦
L---/----
"Вт."- втолкнуть в магазин символ
"Выт."- вытолкнуть из магазина верхний символ
"0"- оставить магазин без изменения
"П"-переход к следующему символу входной цепочки
"Д"- держать текущий символ входной цепочки
"Si"- перейти в состояние
Ряд ячеек управляющей таблицы может без деления на поля заполняться символом Е (состояние ошибки). Если МП-распознаватель попал в такое состояние, то обработка цепочки прекращается и такая цепочка отвергается.
Пример: Постpоить МП-pаспознаватель для pаспознания множеств следующего вида : {0(n) 1(n) ¦ n>0}.
Построим стратегию работы МП-автомат для распознания задан
1.Первыми МП-автомат ожидает прихода серии "0".
2.Поступление каждого "0" сопровождается вталкиванием в магазин символа А для того, чтобы запомнить их количество и сравнить потом с количеством "1".
3.После поступления первой "1" ,нули не должны поступать.
4.Поступление "1" сопровождается выталкиванием из магазина А.Таким образом контролируется равенство количества "0" и "1".Цепочка до-
пускается , если при поступлении "-+" магазин будет пустым.
Зададим МП-автомат:
1. Множество входных символов {0,1,-+};
2. Множество магазинных символов {/,А};
3. Множество состояний {S1,S2}.
4. Hачальная конфигурация - состояние S1, магазин пуст.
Таблица переходов имеет вид (Е-состояние ошибки):
----------T---------T---T-----¬
¦ 0 ¦ 1 ¦ -+ ¦
-------T------+---------+---------+---------+
¦ ¦ ¦ Вт. А /¦ ¦ ¦
¦ ¦ / ¦ / ¦ Е ¦ Отв. ¦
¦ ¦ ¦ S1 / П¦ ¦ ¦
¦ S1 +------+----/ --+---------+---------+
¦ ¦ ¦ Вт.А /¦ Выт.А /¦ ¦
¦ ¦ А ¦ / ¦ / ¦ Отв. ¦
¦ ¦ ¦S1 / П¦S2 / П¦ ¦
+------+------+----/---+----/---+---------+
¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ / ¦ Е ¦ Е ¦ Доп. ¦
¦ ¦ ¦ ¦ ¦ ¦
¦ S2 +------+---------+---------+---------+
¦ ¦ ¦ ¦ Выт.А /¦ ¦
¦ ¦ А ¦ Е ¦ / ¦ Отв. ¦
¦ ¦ ¦ ¦S2 / П¦ ¦
L------+------+---------+----/---+----------
Разберем цепочку 0011-+ с помощью МП-автомата:
г===========T=============T===========¬
¦ Цепочка ¦ Состояние ¦ Магазин ¦
¦-----------+-------------+-----------¦
¦ 0011-+ ¦ S1 ¦ / ¦
¦ ¦ ¦ ¦
¦ 011-+ ¦ S1 ¦ А / ¦
¦ ¦ ¦ ¦
¦ 11-+ ¦ S1 ¦ А А / ¦
¦ ¦ ¦ ¦
¦ 1-+ ¦ S2 ¦ А / ¦
¦ ¦ ¦ ¦
¦ -+ ¦ S2 ¦ / ¦
¦ ¦ ¦ ¦
L===========¦=============¦===========-
Цепочка допущена т.к. конечная конфигурация МП-автоматадопускающая (состояние S2, в магазине пусто).