비주기 유한 상태 오토마톤
Aperiodic finite state automaton비주기적 유한 상태 오토마톤(counter-free automaton이라고도 함)은 전이 모노이드가 비주기적인 유한 상태 오토마톤이다.
특성.
정규언어는 유한하고 비주기적인 전이모노이드를 가진 오토마톤에 의해 받아들여지는 경우에만 별이 없다.이 대수적 오토마타 이론의 결과는 마르셀-폴 쉬첸베르거에 [1]기인한다.특히, 별이 없는 언어의 최소 오토마톤은 항상 카운터 프리입니다(단, 별이 없는 언어는 비주기적인 다른 오토마타에 의해 인식될 수도 있습니다).
카운터가 없는 언어는 정수 n이 존재하여 모든 단어 x, y, z 및 정수 mµn에 대해 xyz가n L에 있는 경우에만 L에 xyz가m 있는 정규 언어입니다.Schützenberger의 정리를 말하는 또 다른 방법은 별이 없는 언어와 반점이 없는 언어는 [further explanation needed]같다는 것이다.
레퍼런스
- ^ Schützenberger, Marcel-Paul (1965). "On Finite Monoids Having Only Trivial Subgroups" (PDF). Information and Control. 8 (2): 190–194. doi:10.1016/s0019-9958(65)90108-7.
- ^ Trahtman, Avraham N. (2007). "The Černý conjecture for aperiodic automata". Discrete Math. Theor. Comput. Sci. 9 (2): 3–10. ISSN 1365-8050. Zbl 1152.68461. Archived from the original on 2015-09-23. Retrieved 2014-04-05.
- McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph. Vol. 65. With an appendix by William Henneman. MIT Press. ISBN 0-262-13076-9. Zbl 0232.94024.
- Sonal Pratik Patel (2010). An Examination of Counter-Free Automata (PDF) (Masters Thesis). San Diego State University. - 맥노튼, 페이퍼트(1971년)의 집중 조사.
- Thomas Colcombet (2011). "Green's Relations and their Use in Automata Theory". In Dediu, Adrian-Horia; Inenaga, Shunsuke; Martín-Vide, Carlos (eds.). Proc. Language and Automata Theory and Applications (LATA) (PDF). LNCS. Vol. 6638. Springer. pp. 1–21. ISBN 978-3-642-21253-6. - Green의 관계를 사용하여 Schützenberger 및 기타 이론을 증명합니다.
