править] Пример с использованием автомата с магазинной памятью

[править] Пример с использованием автомата с магазинной памятью

repeat X:=верхний символ магазина;

if X - терминал или $

then if X=InSym

then удалить X из магазина;

InSym:=очередной символ;

else error()

end

else /* X = нетерминал */

if M[X,InSym]=X->Y1Y2...Yk

then удалить X из магазина;

поместить Yk,Yk-1,...Y1 в магазин

(Y1 на верхушку);

вывести правило X->Y1Y2...Yk

else error() /* вход таблицы M пуст */

end end

until X=$ /* магазин пуст */

[править] Виды автоматов с магазинной памятью

Существуют детерминированные и недетерминированные автоматы с магазинной памятью.

Для недетерминированных автоматов (в отличие от детерминированных) существует два эквивалентных критерия завершения работы:

Детерминированный автомат завершает работу лишь тогда, когда достигает конечного состояния.

[править] Литература

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.

Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её.