Апериодический конечный автомат - Aperiodic finite state automaton

An апериодический конечный автомат (также называемый автомат без счетчика) это конечный автомат чей переходный моноид является апериодический.

Характеристики

А обычный язык является без звезд тогда и только тогда, когда это принимается автоматом с конечным и апериодическим переходный моноид. Этот результат алгебраической теория автоматов связано с Марсель-Пауль Шютценбергер.^[1]В частности, минимальный автомат языка без звездочек всегда свободен от счетчиков (однако язык без звезд может также распознаваться другими автоматами, которые не являются апериодическими).

А свободный язык это обычный язык, для которого есть целое число п так что для всех слов Икс, у, z и целые числа м ≥ п у нас есть ху^мz в L если и только если ху^пz в L. Другой способ сформулировать теорему Шютценбергера состоит в том, что языки без звезд и языки без счетчиков - это одно и то же.

Апериодический автомат удовлетворяет Гипотеза Черного.^[2]

Рекомендации

1. Шютценбергер, Марсель-Поль (1965). «О конечных моноидах, имеющих только тривиальные подгруппы» (PDF). Информация и контроль. 8 (2): 190–194. Дои:10.1016 / с0019-9958 (65) 90108-7.
2. Трахтман, Авраам Н. (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. - Использует Отношения Грина для доказательства теорем Шютценбергера и других.