317
правок
Изменения
Нет описания правки
{{Определение
|definition =
}}
==Пример==
Построим для языка:
# <tex> S \rightarrow 1H </tex>
# <tex> H \rightarrow 0F </tex>
# <tex> H \rightarrow \varepsilon </tex>
# <tex> F \rightarrow 0F </tex>
# <tex> F \rightarrow 1F </tex>
# <tex> F \rightarrow \varepsilon </tex>
автомат <tex>A=(\{0,1\}, \{Z_0,X\}, \{q,p\}, q, \{p\}, Z_0, \delta)</tex> с функией перехода <tex>\delta</tex>:
# <tex>\delta(q,0,Z_0)=(q,XZ_0)</tex>
# <tex>\delta(q,0,X) =(q,XX)</tex>
# <tex>\delta(q,1,X) =(q,X)</tex>
# <tex>\delta(q,1,Z_0)=(p,Z_0)</tex>
# <tex>\delta(p,0,Z_0)=(p,XZ_0)</tex>
# <tex>\delta(p,0,X) =(p,XX)</tex>
# <tex>\delta(p,1,X) =(p,X)</tex> <br> <br>
[[Файл:Пример_мп-автомата.png]]
== См. также ==
* [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
* [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
* [[ДМП-автоматы и неоднозначность]]
== Источники информации ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528с. : ISBN 978-5-8459-1347-0 (рус.)
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: МП-автоматы]]