Апериодты ақырлы күй автоматы - Aperiodic finite state automaton - Wikipedia

Ан апериодты ақырлы күйдегі автомат (а деп те аталады қарсы тегін автомат) Бұл ақырғы күйдегі автомат кімдікі ауыспалы моноидты болып табылады апериодикалық.

Қасиеттері

A тұрақты тіл болып табылады жұлдызсыз егер ол ақырлы және апериодты автоматтармен қабылданса ғана ауыспалы моноидты. Бұл алгебралық нәтиже автоматтар теориясы байланысты Марсель-Пол Шютценбергер.[1]Атап айтқанда, минималды автомат жұлдызсыз тіл әрқашан қарсы болады (сонымен бірге жұлдызсыз тілді апериодты емес басқа автоматтар да тани алады).

A қарсы тіл бұл бүтін сан болатын тұрақты тіл n барлық сөздер үшін х, ж, з және бүтін сандар мn Бізде бар xyмз жылы L егер және егер болса xynз жылы L. Шицценбергер теоремасын айтудың тағы бір тәсілі - жұлдызсыз тілдер мен контр-еркін тілдер бір нәрсе.

Апериодты автоматты қанағаттандырады Černý болжам.[2]

Әдебиеттер тізімі

  1. ^ Шутценбергер, Марсель-Пол (1965). «Тек кішігірім кіші топтары бар ақырғы моноидтар туралы» (PDF). Ақпарат және бақылау. 8 (2): 190–194. дои:10.1016 / s0019-9958 (65) 90108-7.
  2. ^ Трахтман, Авраам Н. (2007). «Апериодты автоматтарға арналған Черный гипотезасы». Дискретті математика. Теория. Есептеу. Ғылыми. 9 (2): 3–10. ISSN  1365-8050. Zbl  1152.68461. Архивтелген түпнұсқа 2015-09-23. Алынған 2014-04-05.