Детерминированные автоматы с магазинной памятью, допуск по пустому стеку — различия между версиями
Zernov (обсуждение | вклад) |
Zernov (обсуждение | вклад) (→Источники) |
||
Строка 21: | Строка 21: | ||
==Источники== | ==Источники== | ||
− | *Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд | + | * ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. : ISBN 978-5-8459-1347-0 (рус.) |
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Контекстно-свободные грамматики]] | [[Категория: Контекстно-свободные грамматики]] | ||
[[Категория: МП-автоматы]] | [[Категория: МП-автоматы]] |
Версия 14:21, 20 ноября 2016
Определение: |
Определим детерминированный автомат с магазинной памятью, допускающий по пустому стеку, как детерминированный автомат с магазинной памятью, у которого нет множества допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым. |
Определим для него множество допускающих слов
, где — произвольное состояние.Определение: |
Язык называется беспрефиксным, если для любой пары слов из этого языка ни одно из этих слов не является префиксом другого. |
Источники
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. : ISBN 978-5-8459-1347-0 (рус.)