Aperiodisk finita tillståndsautomat

En aperiodisk finita-tillståndsautomat (även kallad en counter-free automaton ) är en finite-state automat vars övergångsmonoid är aperiodisk .

Egenskaper

Ett vanligt språk är stjärnfritt om och bara om det accepteras av en automat med en ändlig och aperiodisk övergångsmonoid . Detta resultat av algebraisk automatteori beror på Marcel-Paul Schützenberger . I synnerhet minimiautomaten för ett stjärnfritt språk alltid kontrafritt (ett stjärnfritt språk kan dock även kännas igen av andra automater som inte är aperiodiska).

Ett motfritt språk är ett reguljärt språk för vilket det finns ett heltal n så att vi för alla ord x , y , z och heltal m ≥ n har xy ^m z i L om och bara om xy ⁿ z i L . Ett annat sätt att uttrycka Schützenbergers teorem är att stjärnfria språk och motfria språk är samma sak.

En aperiodisk automat uppfyller Černýs gissning .

•    McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata . Forskningsmonografi. Vol. 65. Med bilaga av William Henneman. MIT Press. ISBN 0-262-13076-9 . Zbl 0232.94024 .
• Sonal Pratik Patel (2010). En undersökning av Counter-Free Automata (PDF) (Masteruppsats). San Diego State University. — En intensiv granskning av McNaughton, Papert (1971).
•   Thomas Colcombet (2011). "Greens relationer och deras användning i automatteori". I Dediu, Adrian-Horia; Inenaga, Shunsuke; Martín-Vide, Carlos (red.). Proc. Språk- och automatteori och tillämpningar (LATA) (PDF) . LNCS. Vol. 6638. Springer. s. 1–21. ISBN 978-3-642-21253-6 . — Använder Greens relationer för att bevisa Schützenbergers och andra satser.