Апериодический конечный автомат
Апериодический конечный автомат (также называемый автоматом без счетчика ) — это конечный автомат, которого моноид перехода является апериодическим .
Характеристики
[ редактировать ]Регулярный язык беззвезден тогда и только тогда , когда он принимается автоматом с конечным и апериодическим переходным моноидом . Этот результат алгебраической теории автоматов принадлежит Марселю-Полю Шютценбергеру . [1] В частности, минимальный автомат бесзвездного языка всегда бессчетен (однако беззвездный язык может распознаваться и другими автоматами, не являющимися апериодическими).
Язык без счетчиков — это регулярный язык, для которого существует целое число n такое, что для всех слов x , y , z и целых чисел m ≥ n имеем xy м z в L тогда и только тогда, когда xy н г в л . Для этих языков, когда строка содержит достаточно повторений любой подстроки (не менее n повторений), изменение количества повторений на другое число, равное хотя бы n, не может изменить принадлежность к языку. (Это автоматически верно, когда y — пустая строка , но становится нетривиальным условием, когда y не пусто.) Другой способ сформулировать теорему Шютценбергера состоит в том, что языки без звезд и языки без счетчиков — это одно и то же.
Апериодический автомат удовлетворяет гипотезе Черного . [2]
Ссылки
[ редактировать ]- ^ Шютценбергер, Марсель-Поль (1965). «О конечных моноидах, имеющих только тривиальные подгруппы» (PDF) . Информация и контроль . 8 (2): 190–194. дои : 10.1016/s0019-9958(65)90108-7 .
- ^ Трахтман, Авраам Н. (2007). «Гипотеза Черного для апериодических автоматов» . Дискретная математика. Теор. Вычислить. наук. 9 (2): 3–10. ISSN 1365-8050 . Збл 1152.68461 . Архивировано из оригинала 23 сентября 2015 г. Проверено 5 апреля 2014 г.
- Макнотон, Роберт; Паперт, Сеймур (1971). Автоматы без счетчиков . Научная монография. Том. 65. С приложением Уильяма Хеннемана. МТИ Пресс. ISBN 0-262-13076-9 . Збл 0232.94024 .
- Сонал Пратик Патель (2010). Исследование автоматов без счетчиков (PDF) (магистерская диссертация). Государственный университет Сан-Диего. - Интенсивное исследование Макнотона, Паперта (1971).
- Томас Колкомбет (2011). «Отношения Грина и их использование в теории автоматов». В Дедью Адриан-Хориа; Иненага, Сюнсукэ; Мартин-Виде, Карлос (ред.). Учеб. Теория и приложения языка и автоматов (LATA) (PDF) . ЛНКС. Том. 6638. Спрингер. стр. 1–21. ISBN 978-3-642-21253-6 . - Использует соотношения Грина для доказательства Шютценбергера и других теорем.