РАЗНОЗНОВИДНОСТИ МП-АВТОМАТОВ
Иногда определяют МП-автомат, который принимает строку, если после завершения ее чтения стек автомата буде пуст. В этом случае нет необходимости выделять множество заключительных состояний автомата FÍQ, а описание заключитеотной конфигурации имеет вид (q, e , e), где q ÎQ. Говорят, что такой МП-автомат принимает строку языка опустошением магазина.
Пример.МП-автомат Р=(Q={A}, S={(, )}, Г=(I, O), q0=A, Z0=I),
в котором функция переходов определяется следующим образом:
| 1) d(A, (, I)={(A,OI)} |
| 2) d(A, (, O)={(A, OO)} |
| 3) d(A, ), O)={(A, e)} |
| 4) d(A, e, I)={ (A, e)} |
При распознавании строки ( ( ) ( ) ) строит последовательность конфигураций:
(A, ( ( ) ( ) ), I) ├ (A, ( ) ( ) ), OI) ├ (A, ) ( ) ), OOI) ├ (A, ( ) ), OI) ├ (A, ) ), OOI) ├
(A, ), OI) ├ (A, e , I) ├(A, e, e)
Язык, принимаемый МП-автоматом в данном примере, это КС-язык парных круглых скобок. Этот же язык генерирует КС-грамматика с правилами P={S®(S), S®SS, S®e}.
Из формального определения МП-автомата следует, что он может менять каждый раз только один символ в вершине стека. Этот МП-автомат не может, кроме того, продолжать работу при пустом стеке, так как e Ï Г. Однако, если использовать расширенный МП-автомат, то указанные ограничения будут сняты.
МП-автомат называется детерминированным (ДМП-автоматом), если, находясь в любой конфигурации, он может выбрать не более одной следующей конфигурации. В противном случае МП-автомат называется недерминированным.