WikiDer > Апериодический конечный автомат - Википедия
An апериодический конечный автомат (также называемый автомат без счетчика) это конечный автомат чей переходный моноид является апериодический.
Характеристики
А обычный язык является без звезд тогда и только тогда, когда это принимается автоматом с конечным и апериодическим переходный моноид. Этот результат алгебраической теория автоматов связано с Марсель-Пауль Шютценбергер.[1]В частности, минимальный автомат языка без звездочек всегда свободен от счетчиков (однако язык без звезд может также распознаваться другими автоматами, которые не являются апериодическими).
А свободный язык это обычный язык, для которого есть целое число п так что для всех слов Икс, у, z и целые числа м ≥ п у нас есть хумz в L если и только если хупz в L. Другой способ сформулировать теорему Шютценбергера состоит в том, что языки без звезд и языки без счетчиков - это одно и то же.
Апериодический автомат удовлетворяет Гипотеза Черного.[2]
Рекомендации
- ^ Шютценбергер, Марсель-Поль (1965). «О конечных моноидах, имеющих только тривиальные подгруппы» (PDF). Информация и контроль. 8 (2): 190–194. Дои:10.1016 / с0019-9958 (65) 90108-7.
- ^ Трахтман, Авраам Н. (2007). "Гипотеза Черни для апериодических автоматов". Дискретная математика. Теор. Comput. Наука. 9 (2): 3–10. ISSN 1365-8050. Zbl 1152.68461. Архивировано из оригинал на 2015-09-23. Получено 2014-04-05.
- Макнотон, Роберт; Паперт, Сеймур (1971). Автоматы без счетчиков. Монография исследований. 65. С приложением Уильяма Хеннемана. MIT Press. ISBN 0-262-13076-9. Zbl 0232.94024.
- Сонал Пратик Патель (2010). Исследование автоматов без встречных (PDF) (Дипломная работа). Государственный университет Сан-Диего. - Интенсивный экзамен McNaughton, Papert (1971).
- Томас Колкомбет (2011). «Отношения Грина и их использование в теории автоматов». В Дедиу Адриан-Хория; Иненага, Сюнсуке; Мартин-Виде, Карлос (ред.). Proc. Теория языков и автоматов и приложения (LATA) (PDF). LNCS. 6638. Springer. С. 1–21. ISBN 978-3-642-21253-6. - Использует Отношения Грина для доказательства теорем Шютценбергера и других.
| P ≟ NP | Этот теоретическая информатика–Связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |