Апериодический конечный автомат
-
Определение и свойства апериодического конечного автомата
- Апериодический конечный автомат — это автомат с апериодическим моноидом перехода.
- Обычный язык без звездочек распознается апериодическим автоматом.
- Минимальный автомат языка без звездочек контр-свободен.
-
Теорема Шютценбергера
- Язык без счетчиков — это язык, для которого изменение количества повторов не влияет на принадлежность к языку.
- Языки без звездочек и без счетчиков эквивалентны.
-
Гипотеза Черного
- Апериодический автомат удовлетворяет гипотезе Черного.
-
Рекомендации
- Исследование Макнотона и Паперта (1971) для подробного изучения.
- Использование соотношений Грина для доказательства теорем.
-
Призыв к расширению статьи
- Статья является заглушкой и нуждается в расширении.
- Читателей призывают помочь Википедии, расширив статью.
Полный текст статьи: