Разнозновидности мп-автоматов

Иногда определяют МП-автомат, который принимает строку, если после завершения ее чтения стек автомата буде пуст. В этом случае нет необходимости выделять множество заключительных состояний автомата 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 Ï Г. Однако, если использовать расширенный МП-автомат, то указанные ограничения будут сняты.

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

Дата добавления: 2014-01-03