Regelmäßige Sprache

Für die regulierte natürliche Sprache siehe Liste der Sprachregulierungsbehörden.
"Kleene's Theorem" leitet hier weiter. Für seine Theoreme für rekursive Funktionen siehe Kleenes Rekursionstheorem.

Im Theoretische Informatik und Formale Sprachtheorie, a Regelmäßige Sprache (auch a genannt Rationale Sprache)[1][2] ist ein formelle Sprache das kann durch a definiert werden regulären Ausdruckim strengen Sinne der theoretischen Informatik (im Gegensatz zu vielen modernen regulären Ausdrucksmotoren, die sind mit Funktionen erweitert die Erkennung nichtregulärer Sprachen ermöglichen).

Alternativ kann eine reguläre Sprache als eine von a erkannte Sprache definiert werden Finite Automaton. Die Äquivalenz regelmäßiger Ausdrücke und endlicher Automata ist als bekannt als Kleene's Theorem[3] (Nach dem amerikanischen Mathematiker Stephen Cole Kleene). In dem Chomsky -Hierarchie, reguläre Sprachen sind die Sprachen, die von generiert werden, Typ-3-Grammatiken.

Formale Definition

Die Sammlung regulärer Sprachen über eine Alphabet Σ wird rekursiv wie folgt definiert:

  • Die leere Sprache Ø ist eine reguläre Sprache.
  • Für jeden a ∈ σ (a gehört zu σ), die Singleton Sprache {a} ist eine reguläre Sprache.
  • Wenn A ist eine reguläre Sprache, A* (Kleene Star) ist eine reguläre Sprache. Aus diesem Grund ist auch die leere Stringsprache {ε} regelmäßig.
  • Wenn A und B sind reguläre Sprachen dann A ∪ B (Gewerkschaft) und A • B (Verkettung) sind reguläre Sprachen.
  • Keine anderen Sprachen über σ sind regelmäßig.

Sehen regulären Ausdruck Für die Syntax und Semantik regelmäßiger Ausdrücke.

Beispiele

Alle endlichen Sprachen sind regelmäßig; insbesondere die leerer String Sprache {ε} = Ø* ist regelmäßig. Andere typische Beispiele sind die Sprache, die aus allen Zeichenfolgen über dem Alphabet besteht {a, b} die eine gleichmäßige Anzahl von enthält as oder die Sprache, die aus allen Zeichenfolgen der Form besteht: mehrere as gefolgt von mehreren bs.

Ein einfaches Beispiel für eine Sprache, die nicht regelmäßig ist, ist der Satz von Strings { anbn | n ≥ 0}.[4] Intuitiv kann es nicht mit einem endlichen Automaten erkannt werden, da ein endlicher Automaton ein endliches Speicher hat und sich nicht an die genaue Anzahl von A erinnern kann. Techniken, um diese Tatsache streng zu beweisen, werden gegeben unter.

Äquivalente Formalismen

Eine reguläre Sprache erfüllt die folgenden äquivalenten Eigenschaften:

  1. Es ist die Sprache eines regulären Ausdrucks (nach der obigen Definition)
  2. Es ist die von a akzeptierte Sprache Nichtdeterministisches endliches Automaten (NFA)[Anmerkung 1][Anmerkung 2]
  3. Es ist die von a akzeptierte Sprache Deterministische endliche Automaten (DFA)[Notiz 3][Anmerkung 4]
  4. es kann durch a generiert werden Regelmäßige Grammatik[Anmerkung 5][Anmerkung 6]
  5. Es ist die Sprache, die von einem akzeptiert wird Wechsels endlicher Automaten
  6. Es ist die von a akzeptierte Sprache Zwei-Wege-endliche Automaten
  7. es kann durch a generiert werden Präfix Grammatik
  8. Es kann von einem schreibgeschützten Bereich akzeptiert werden Turing Maschine
  9. es kann in definiert werden in monadisch Logik zweiter Ordnung (Büchi -Elgot -Trakhtenbrot Theorem)[5]
  10. es ist anerkannt von einigen endlichen syntaktisches Monoid M, was bedeutet, dass es das ist Vorbereitung { w ∈ σ* | f(w) ∈ S } einer Untergruppe S eines endlichen Monoids M unter einem Monoid -Homomorphismus f: Σ* → M von dem Freies Monoid auf seinem Alphabet[Anmerkung 7]
  11. die Anzahl der Äquivalenzklassen seiner syntaktische Kongruenz ist endlich.[Anmerkung 8][Anmerkung 9] (Diese Zahl entspricht der Anzahl der Zustände der Zustände der Minimal deterministische endliche Automatik Akzeptieren L.))

Eigenschaften 10. und 11. sind rein algebraische Ansätze zur Definition regulärer Sprachen; Ein ähnlicher Satz von Aussagen kann für ein Monoid formuliert werden M ⊆ σ*. In diesem Fall gleichwertig über M führt zum Konzept einer erkennbaren Sprache.

Einige Autoren verwenden eine der oben genannten Eigenschaften als "1.". als alternative Definition von regulären Sprachen.

Einige der oben genannten Äquivalenzen, insbesondere die ersten vier Formalismen, werden genannt Kleene's Theorem in Lehrbüchern. Genau welches (oder welche Teilmenge) so genannt wird, variiert zwischen den Autoren. Ein Lehrbuch nennt die Äquivalenz regulärer Ausdrücke und NFAs ("1." und "2." oben) "Kleene's Theorem".[6] Ein anderes Lehrbuch nennt die Äquivalenz regulärer Ausdrücke und DFAs ("1." und "3." oben "Kleene's Theorem".[7] Zwei weitere Lehrbücher beweisen zunächst die ausdrucksstarke Äquivalenz von NFAs und DFAS ("2." und "3.") und geben dann Kleenes Theorem "als Äquivalenz zwischen regulären Ausdrücken und endlichen Automata (letztere" als "erkennbare Sprachen") an. .[2][8] Ein sprachlich orientierter Text entspricht zuerst regelmäßige Grammatiken ("4." oben) mit DFAs und NFAs, nennt die von (beliebten) diese "regulären" generierten Sprachen, wonach er reguläre Ausdrücke einführt, die er bezeichnet, um "rationale Sprachen" zu beschreiben, Und schließlich heißt es "Kleene's Theorem" als Zufall der regulären und rationalen Sprachen.[9] Andere Autoren einfach definieren "rationaler Ausdruck" und "reguläre Ausdrücke" als Synonym und das Gleiche mit "rationalen Sprachen" und "regulären Sprachen".[1][2]

Anscheinend der Begriff "regulär" stammt aus einem technischen Bericht von 1951, in dem Kleene eingeführt wurde "reguläre Veranstaltungen" und explizit begrüßt "Alle Vorschläge zu einem beschreibenderen Begriff".[10] Noam Chomskyverwendete in seinem wegweisenden Artikel von 1959 den Begriff "regulär" zunächst in einer anderen Bedeutung (in Bezug auf das, was genannt wird "Chomsky Normale Form" heute),[11] bemerkte aber, dass seine sein "Endliche Zustandssprachen" waren Kleene's äquivalent "reguläre Veranstaltungen".[12]

Verschlusseigenschaften

Die regulären Sprachen sind abgeschlossen Unter verschiedenen Operationen, das heißt, wenn die Sprachen K und L sind regelmäßig, ebenso das Ergebnis der folgenden Operationen:

  • das Set-theoretische booleale Operationen: Union K ∪ L, Überschneidung K ∩ L, und ergänzen Ldaher auch relative Ergänzung K − L.[13]
  • die regulären Operationen: K ∪ L, Verkettung , und Kleene Star L*.[14]
  • das Trio Operationen: String -Homomorphismus, inverse String -Homomorphismus und Schnittpunkt mit regulären Sprachen. Infolgedessen sind sie unter willkürlich geschlossen Finite -Status -Transduktionen, wie Quotient K / L mit einer regulären Sprache. Noch mehr, reguläre Sprachen werden unter Quoten mit geschlossen willkürlich Sprachen: if L ist dann regelmäßig L / K ist regelmäßig für jeden K.
  • das umgekehrte (oder Spiegelbild) LR.[15] Angesichts eines nichtdeterministischen endlichen Automaten L, ein Automat für LR Kann durch Umkehrung aller Übergänge und den Austausch von Start- und Endzuständen erhalten werden. Dies kann zu mehreren Startzuständen führen. ε-Übergang können verwendet werden, um sich ihnen anzuschließen.

Dekidabilitätseigenschaften

Bei zwei deterministischen endlichen Automaten A und BEs ist lehnte, ob sie dieselbe Sprache akzeptieren.[16] Infolgedessen verwenden Sie die Oben Verschlusseigenschaften sind die folgenden Probleme auch für willkürlich beschwindige deterministische endliche Automaten entschlossen A und B, mit akzeptierten Sprachen LA und LB, beziehungsweise:

  • Eindämmung: IS LA ⊆ LB?[Anmerkung 10]
  • Disjunktizität: IS LA ∩ LB = {}?
  • Leere: IS LA = {}?
  • Universalität: ist LA = Σ*?
  • Mitgliedschaft: gegeben a ∈ σ*, ist a ∈ LB?

Für reguläre Ausdrücke ist das Universalitätsproblem NP-Complete Bereits für ein Singleton -Alphabet.[17] Für größere Alphabete ist dieses Problem PSPACE-Complete.[18] Wenn reguläre Ausdrücke erweitert werden, um auch a zuzulassen Quadratbetreiber, mit "A2"Das gleiche wie"Aa", immer noch reguläre Sprachen können beschrieben werden, aber das Universalitätsproblem hat einen exponentiellen Raum unter Grenze.[19][20][21] und ist tatsächlich für exponentielle Raum in Bezug auf die Reduzierung der Polynomzeit vollständig.[22]

Komplexitätsergebnisse

Im Computerkomplexitätstheorie, das Komplexitätsklasse von allen regulären Sprachen wird manchmal als bezeichnet REGULÄR oder Regs und gleich DSpace(O (1)), die Entscheidungsprobleme Dies kann im konstanten Raum gelöst werden (der verwendete Raum ist unabhängig von der Eingangsgröße). REGULÄR ≠ AC0Da es (trivial) das Paritätsproblem enthält, um festzustellen, ob die Anzahl der 1 Bit im Eingang gerade oder ungerade ist und dieses Problem nicht in ist AC0.[23] Auf der anderen Seite, REGULÄR beinhaltet nicht AC0, weil die nichtreguläre Sprache von Palindrome, oder die nichtreguläre Sprache kann beide in erkannt werden in AC0.[24]

Wenn eine Sprache ist nicht Regelmäßig erfordert es eine Maschine mit zumindest Ω(Protokollprotokoll n) Raum zu erkennen (wo n ist die Eingangsgröße).[25] Mit anderen Worten, DSpace (o(Protokollprotokoll n)) entspricht der Klasse der regulären Sprachen. In der Praxis werden die meisten nichtregulären Probleme von Maschinen gelöst, die zumindest einnehmen logarithmischer Raum.

Lage in der Chomsky -Hierarchie

Regelmäßige Sprache in Klassen der Chomsky -Hierarchie.

Um die regulären Sprachen in der zu finden Chomsky -HierarchieMan merkt, dass jede reguläre Sprache ist kontextfrei. Das Gegenteil ist nicht wahr: Zum Beispiel die Sprache, die aus allen Zeichenfolgen besteht a's as b'S ist kontextfrei, aber nicht regelmäßig. Um zu beweisen, dass eine Sprache nicht regelmäßig ist, verwendet man oft die Myhill -Nerode -Theorem und die Lemma pumpen. Andere Ansätze sind die Verwendung der Verwendung der Verschlusseigenschaften von regulären Sprachen[26] oder quantifizieren Kolmogorov -Komplexität.[27]

Wichtige Unterklassen regulärer Sprachen umfassen

  • Endliche Sprachen, die nur eine endliche Anzahl von Wörtern enthalten.[28] Dies sind reguläre Sprachen, da man a erstellen kann regulären Ausdruck das ist das Union jedes Wortes in der Sprache.
  • Sternfreie Sprachen, diejenigen, die durch einen regulären Ausdruck beschrieben werden können, der aus dem leeren Symbol, den Buchstaben, der Verkettung und allen booleschen Operatoren konstruiert ist (siehe Algebra der Sets) einschließlich Ergänzung aber nicht das Kleene Star: Diese Klasse enthält alle endlichen Sprachen.[29]

Die Anzahl der Wörter in einer regulären Sprache

Lassen Bezeichnen Sie die Anzahl der Längenwörter in . Das Gewöhnliche Erzeugungsfunktion zum L ist der Formale Machtserie

Die Erzeugungsfunktion einer Sprache L ist ein rationale Funktion wenn L ist regelmäßig.[30] Daher für jede reguläre Sprache die Sequenz ist konstant rekursiv; Das heißt, es gibt eine Ganzzahlkonstante , komplexe Konstanten und komplexe Polynome so dass für jeden die Nummer von Längenwörtern in ist.[31][32][33][34]

Daher die Nichtregularität bestimmter Sprachen kann durch Zählen der Worte einer bestimmten Länge in beweist werden. Betrachten Sie zum Beispiel die Dyck -Sprache von Saiten ausgewogener Klammern. Die Anzahl der Länge der Wörter in der Dyck -Sprache ist gleich der Katalanische Nummer , was nicht von der Form ist , Zeuge der Nichtregularität der Dyck-Sprache. Es muss vorsichtig sein, da einige der Eigenwerte könnte die gleiche Größe haben. Zum Beispiel die Anzahl der Länge der Wörter In der Sprache aller sogar binären Wörter ist nicht die Form , aber die Anzahl der Wörter der geraden oder ungeraden Länge ist von dieser Form; Die entsprechenden Eigenwerte sind . Im Allgemeinen gibt es für jede reguläre Sprache eine Konstante so dass für alle , die Anzahl der Wörter der Länge ist asymptotisch .[35]

Das Zeta -Funktion einer Sprache L ist[30]

Die Zeta -Funktion einer regulären Sprache ist nicht allgemein rational, sondern die eines willkürlichen zyklische Sprache ist.[36][37]

Verallgemeinerungen

Der Begriff einer regulären Sprache wurde auf unendliche Wörter verallgemeinert (siehe ω-automata) und zu Bäumen (siehe Baumautomaton).

Rational Set verallgemeinert den Begriff (der regulären/rationalen Sprache) auf Monoide, die nicht unbedingt sind frei. Ebenso hat der Begriff einer erkennbaren Sprache (durch einen endlichen Automaten) den Namensvetter als erkennbarer Satz über einem Monoid, das nicht unbedingt frei ist. Howard Strabing Notizen in Bezug auf diese Tatsachen, dass "der Begriff" reguläre Sprache "etwas unglücklich ist. Papiere beeinflusst von EilenbergMonographie[38] Verwenden Sie häufig entweder den Begriff "erkennbare Sprache", der sich auf das Verhalten von Automaten oder "rationale Sprache" bezieht, was sich auf wichtige Analogien zwischen regulären Ausdrücken und rationalen Kraftreihen bezieht. (Tatsächlich definiert Eilenberg rationale und erkennbare Teilmengen willkürlicher Monoide; die beiden Begriffe fällt im Allgemeinen nicht zusammen.) Diese Terminologie, obwohl sie besser motiviert, nie wirklich erwischt und "reguläre Sprache" fast universell verwendet wird. "[39]

Rationale Serie ist eine weitere Verallgemeinerung, diesmal im Kontext von a Formale Power -Serie über eine Semrierung. Dieser Ansatz führt zu gewichteten rationalen Ausdrücken und Gewichtete Automaten. In diesem algebraischen Kontext die regulären Sprachen (entspricht Boolesche-Wichtete rationale Ausdrücke werden normalerweise genannt Rationale Sprachen.[40][41] Ebenfalls in diesem Zusammenhang findet Kleenes Theorem eine Generalisierung, die als Kleene-Schützenberger-Theorem bezeichnet wird.

Lernen aus Beispielen

Hauptartikel: Induktion regulärer Sprachen

Anmerkungen

  1. ^ 1. ⇒ 2. von Thompsons Baualgorithmus
  2. ^ 2. ⇒ 1. durch Kleenes Algorithmus oder verwenden Ardens Lemma
  3. ^ 2. ⇒ 3. nach dem Poweret -Konstruktion
  4. ^ 3. ⇒ 2. Seit ersteren Definition ist stärker als die letztere
  5. ^ 2. ⇒ 4. Siehe Hopcroft, Ullman (1979), Theorem 9.2, S.219
  6. ^ 4. ⇒ 2. Siehe Hopcroft, Ullman (1979), Theorem 9.1, S.218
  7. ^ 3. ⇔ 10. von der Myhill -Nerode -Theorem
  8. ^ u~v ist definiert als: UW∈L dann und nur dann, wenn VW∈L für alle w∈σ*
  9. ^ 3. ⇔ 11. Siehe den Beweis in der Syntaktisches Monoid Artikel und siehe S.160 in Holcombe, W.M.L. (1982). Algebraische Automatentheorie. Cambridge -Studien zur fortgeschrittenen Mathematik. Vol. 1. Cambridge University Press. ISBN 0-521-60492-3. Zbl 0489.68046.
  10. ^ Überprüfen Sie, ob LA ∩ LB = LA. Die Entscheidung dieser Eigenschaft ist Np-harte Im Algemeinen; Siehe Datei: Regsubsetnp.pdf für eine Abbildung der Beweisidee.

Verweise

  1. ^ a b Ruslan Mitkov (2003). Das Oxford -Handbuch der Computer -Linguistik. Oxford University Press. p. 754. ISBN 978-0-19-927634-9.
  2. ^ a b c Mark V. Lawson (2003). Finite Automaten. CRC Press. S. 98–103. ISBN 978-1-58488-255-8.
  3. ^ Sheng Yu (1997). "Reguläre Sprachen". In Grzegorz Rozenberg; Arto Salomaa (Hrsg.). Handbuch der formalen Sprachen: Band 1. Wort, Sprache, Grammatik. Springer. p. 41. ISBN 978-3-540-60420-4.
  4. ^ Eilenberg (1974), p. 16 (Beispiel II, 2.8) und p. 25 (Beispiel II, 5.2).
  5. ^ M. Weyer: Kapitel 12 - Dekidabilität von S1S und S2S, p. 219, Satz 12.26. In: Erich Gräl, Wolfgang Thomas, Thomas Wilke (Hrsg.): Automaten, Logik und unendliche Spiele: Ein Leitfaden für aktuelle Forschungen. Vorlesungsnotizen in Informatik 2500, Springer 2002.
  6. ^ Robert Sedgebick; Kevin Daniel Wayne (2011). Algorithmen. Addison-Wesley Professional. p. 794. ISBN 978-0-321-57351-3.
  7. ^ Jean-Paul Allouche; Jeffrey Sian (2003). Automatische Sequenzen: Theorie, Anwendungen, Verallgemeinerungen. Cambridge University Press. p. 129. ISBN 978-0-521-82332-6.
  8. ^ Kenneth Rosen (2011). Diskrete Mathematik und ihre Anwendungen 7. Ausgabe. McGraw-Hill Science. S. 873–880.
  9. ^ Horst Bunke; Alberto Sanfeliu (Januar 1990). Syntaktische und strukturelle Mustererkennung: Theorie und Anwendungen. Welt wissenschaftlich. p. 248. ISBN 978-9971-5-0566-0.
  10. ^ Stephen Cole Kleene (Dezember 1951). Darstellung von Ereignissen in Nervennetzen und endlicher Automatisierung (PDF) (Forschungsmemorandum). US Air Force / Rand Corporation. Hier: S.46
  11. ^ Noam Chomsky (1959). "Auf bestimmten formalen Eigenschaften von Grammatik" (PDF). Informationen und Kontrolle. 2 (2): 137–167. doi:10.1016/s0019-9958 (59) 90362-6. Hier: Definition 8, S.149
  12. ^ Chomsky 1959, Fußnote 10, S.150
  13. ^ Salomaa (1981) S. 28
  14. ^ Salomaa (1981) S. 27
  15. ^ Hopcroft, Ullman (1979), Kapitel 3, Übung 3.4g, p. 72
  16. ^ Hopcroft, Ullman (1979), Satz 3.8, S. 64; Siehe auch Theorem 3.10, S.67
  17. ^ Aho, Hopcroft, Ullman (1974), Übung 10.14, S. 401
  18. ^ Aho, Hopcroft, Ullman (1974), Satz 10.14, S. 399
  19. ^ Hopcroft, Ullman (1979), Theorem 13.15, S. 351
  20. ^ A.R. Meyer & L. J. Stockmeyer (Oktober 1972). Das Äquivalenzproblem für reguläre Ausdrücke mit Quadrat erfordert einen exponentiellen Raum (PDF). 13. jährliches IEEE Symp. Zum Schalten und Automata -Theorie. S. 125–129.
  21. ^ L. J. Stockmeyer & A.R. Meyer (1973). Wortprobleme, die exponentielle Zeit erfordern (PDF). Proc. 5. Ann. Symp. Zur Theorie des Computers (STOC). ACM. S. 1–9.
  22. ^ Hopcroft, Ullman (1979), Korollar, S. 353
  23. ^ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984). "Parität, Schaltungen und die Polynom-Zeit-Hierarchie". Theorie der mathematischen Systeme. 17 (1): 13–27. doi:10.1007/bf01744431. HERR 0738749. S2CID 14677270.
  24. ^ Kochen, Stephen; Nguyen, Phuong (2010). Logische Grundlagen der Beweiskomplexität (1. Publ. Ed.). Ithaca, NY: Assoziation für symbolische Logik. p. 75. ISBN 978-0-521-51729-4.
  25. ^ J. Hartmanis, P.L. Lewis II. Und R. E. Stearns. Hierarchien von Speicherbeschränkungen. Verfahren des 6. jährlichen IEEE -Symposiums zum Umschalten der Schaltungstheorie und des Logikdesigns, S. 179–190. 1965.
  26. ^ "Wie kann man beweisen, dass eine Sprache nicht regelmäßig ist?". CS.Stackexchange.com. Abgerufen 10. April 2018.
  27. ^ Hromkovič, Juraj (2004). Theoretische Informatik: Einführung in Automaten, Berechnung, Komplexität, Algorithmik, Randomisierung, Kommunikation und Kryptographie. Springer. S. 76–77. ISBN 3-540-14015-8. OCLC 53007120.
  28. ^ Eine endliche Sprache sollte nicht mit einer (normalerweise unendlichen) Sprache verwechselt werden, die von einem endlichen Automaten generiert wird.
  29. ^ Volker Diekert; Paul Gastin (2008). "Definierbare Sprachen erster Ordnung" (PDF). In Jörg Flum; Erich Grädel; Thomas Wilke (Hrsg.). Logik und Automaten: Geschichte und Perspektiven. Amsterdam University Press. ISBN 978-90-5356-576-6.
  30. ^ a b Honkala, Juhha (1989). "Eine notwendige Bedingung für die Rationalität der Zeta -Funktion einer regulären Sprache". Theor. Computer. Sci. 66 (3): 341–347. doi:10.1016/0304-3975 (89) 90159-x. Zbl 0675.68034.
  31. ^ Flajolet & Sedgweick, Abschnitt V.3.1, Gleichung (13).
  32. ^ "Anzahl der Wörter in der regulären Sprache $ (00)^*$". CS.Stackexchange.com. Abgerufen 10. April 2018.
  33. ^ "Beweis des Satzes für willkürliche DFAs".
  34. ^ "Anzahl der Wörter einer bestimmten Länge in einer regulären Sprache". CS.Stackexchange.com. Abgerufen 10. April 2018.
  35. ^ Flajolet & Sedgewick (2002) Theorem V.3
  36. ^ Berstel, Jean; Reuutenauer, Christophe (1990). "Zeta -Funktionen formaler Sprachen". Trans. Bin. Mathematik. SOC. 321 (2): 533–546. Citeseerx 10.1.1.309.3005. doi:10.1090/S0002-9947-1990-0998123-x. Zbl 0797.68092.
  37. ^ Berstel & Reuutenauer (2011) S.222
  38. ^ Samuel Eilenberg. Automaten, Sprachen und Maschinen. Akademische Presse. in zwei Bänden "a" (1974, ISBN9780080873749) und "B" (1976,, ISBN9780080873756), letztere mit zwei Kapiteln von Bret Tilson.
  39. ^ Straubing, Howard (1994). Finite -Automaten, formale Logik und Komplexität der Schaltung. Fortschritte in der theoretischen Informatik. Basel: Birkhäuser. p.8. ISBN 3-7643-3719-2. Zbl 0816.68086.
  40. ^ Berstel & Reuutenauer (2011) S.47
  41. ^ Sakarovitch, Jacques (2009). Elemente der Automata -Theorie. Übersetzt aus den Franzosen von Reuben Thomas. Cambridge: Cambridge University Press. p. 86. ISBN 978-0-521-84425-3. Zbl 1188.68177.

Weitere Lektüre

  • Kleene, S.C.: Darstellung von Ereignissen in Nervennetzen und endlichen Automaten. In: Shannon, C. E., McCarthy, J. (Hrsg.) Automata Studies, S. 3–41. Princeton University Press, Princeton (1956); Es ist eine leicht modifizierte Version seines 1951 Rand Corporation gleichem Bericht, RM704.
  • Sakarovitch, J (1987). "Kleene's Theorem überarbeitet". Trends, Techniken und Probleme in der theoretischen Informatik. Vorlesungsnotizen in Informatik. Vol. 1987. S. 39–50. doi:10.1007/3540185356_29. ISBN 978-3-540-18535-2.

Externe Links