Aperiodický konečný stavový automat - Aperiodic finite state automaton - Wikipedia

An aperiodický konečný stavový automat (také nazývaný a bezplatný automat) je konečný stavový automat jehož přechodový monoid je neperiodické.

Vlastnosti

A běžný jazyk je bez hvězd právě když je akceptován automatem s konečnou a neperiodickou přechodový monoid. Tento výsledek algebraické teorie automatů je to kvůli Marcel-Paul Schützenberger.^[1]Zejména minimální automat bezhvězdného jazyka je vždy proti-volný (bezhvězdný jazyk však mohou rozpoznat i jiné automaty, které nejsou neperiodické).

A bezodkladný jazyk je běžný jazyk, pro který existuje celé číslo n taková, že pro všechna slova X, y, z a celá čísla m ≥ n my máme xy^mz v L kdyby a jen kdyby xyⁿz v L. Dalším způsobem, jak vyjádřit Schützenbergerovu větu, je, že jazyky bez hvězd a jazyky bez svobod jsou totéž.

Aperiodický automat vyhovuje Černý dohad.^[2]

Reference

^ Schützenberger, Marcel-Paul (1965). „Na konečných monoidech, které mají pouze banální podskupiny“ (PDF). Informace a kontrola. 8 (2): 190–194. doi:10.1016 / s0019-9958 (65) 90108-7.
^ Trahtman, Avraham N. (2007). „Černý dohad pro neperiodické automaty“. Diskrétní matematika. Teor. Comput. Sci. 9 (2): 3–10. ISSN 1365-8050. Zbl 1152.68461. Archivovány od originál dne 2015-09-23. Citováno 2014-04-05.

McNaughton, Robert; Papert, Seymour (1971). Bezplatné automaty. Výzkumná monografie. 65. S dodatkem od Williama Hennemana. MIT Stiskněte. ISBN 0-262-13076-9. Zbl 0232.94024.
Sonal Pratik Patel (2010). Zkoumání bezplatných automatů (PDF) (Diplomová práce). Státní univerzita v San Diegu. - Intenzivní zkoumání McNaughtona, Paperta (1971).
Thomas Colcombet (2011). "Greenovy vztahy a jejich použití v teorii automatů". V Dediu, Adrian-Horia; Inenaga, Shunsuke; Martín-Vide, Carlos (eds.). Proc. Teorie a aplikace jazyků a automatů (LATA) (PDF). LNCS. 6638. Springer. s. 1–21. ISBN 978-3-642-21253-6. - Používá Greenovy vztahy dokázat Schützenbergerovy a další věty.

P ≟ NP

Tento teoretická informatika –Vztahující se článek je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[Schutzenberger65-1] Schützenberger, Marcel-Paul (1965). „Na konečných monoidech, které mají pouze banální podskupiny“ (PDF). Informace a kontrola. 8 (2): 190–194. doi:10.1016 / s0019-9958 (65) 90108-7.

[Trahtman07-2] Trahtman, Avraham N. (2007). „Černý dohad pro neperiodické automaty“. Diskrétní matematika. Teor. Comput. Sci. 9 (2): 3–10. ISSN 1365-8050. Zbl 1152.68461. Archivovány od originál dne 2015-09-23. Citováno 2014-04-05.

[1]

[2]