Automatenheorie

Kurs von Automaten

(Klicken auf jede Ebene erhält einen Artikel zu diesem Thema)

Der damit beschriebene Automaten Zustandsdiagramm beginnt im Staat s₁und ändert die Zustände nach den Pfeilen, die 0 oder 1 gemäß den Eingangssymbolen markiert sind. Der Doppelkreis markiert s s₁ Als Akzeptanzstaat. Da alle Wege von s₁ Für sich selbst enthält eine gleichmäßige Anzahl von mit 0 gekennzeichneten Pfeilen, dass dieser Automaton Zeichenfolgen mit einer gleichmäßigen Nummern von 0s akzeptiert.

Automatenheorie ist das Studium von Abstrakte Maschinen und Automaten, ebenso wie Rechenprobleme Das kann mit ihnen gelöst werden. Es ist eine Theorie in Theoretische Informatik. Das Wort Automaten Kommt aus dem griechischen Wort αὐτόματος, was "selbstwirksam, selbstweilt, selbstbewegend" bedeutet. Ein Automaton (Automata im Plural) ist ein abstraktes, selbstgedrucktes Computergerät, das automatisch einer vorgegebenen Abfolge von Operationen folgt. Ein Automat mit einer endlichen Anzahl von Zuständen wird als endlicher Automat (FA) oder Finite-State-Maschine (FSM) bezeichnet. Die Figur rechts zeigt a Finite-State-Maschine, was zu einem bekannten Automaton-Typ gehört. Dieser Automat besteht aus Zustände (in der Abbildung durch Kreise dargestellt) und Übergänge (dargestellt durch Pfeile). Wenn der Automaton ein Symbol der Eingabe sieht, macht er einen Übergang (oder springt) in einen anderen Zustand, je nach seiner Angaben Übergangsfunktion, was den vorherigen Status und aktuellem Eingabemymbol als Argumente nimmt.

Die Automatenheorie ist eng mit dem verwandt mit formelle Sprache Theorie. In diesem Zusammenhang werden Automaten als endliche Darstellungen formaler Sprachen verwendet, die möglicherweise unendlich sein. Automaten werden häufig durch die Klasse der formalen Sprachen klassifiziert, die sie erkennen können, wie in der Chomsky -Hierarchie, die eine Verschachtelungsbeziehung zwischen den wichtigsten Automatenklassen beschreibt. Automaten spielen eine wichtige Rolle in Theorie der Berechnung, Compiler -Konstruktion, künstliche Intelligenz, Parsing und formelle Überprüfung.

Geschichte

Die Theorie der abstrakten Automaten wurde Mitte des 20. Jahrhunderts im Zusammenhang mit Finite Automaten.^[1] Die Automatenheorie wurde ursprünglich als Zweig der mathematischen Zweigstelle angesehen SystemtheorieUntersuchung des Verhaltens von diskreten Parametersystemen. Frühe Arbeiten in der Automatentheorie unterschieden sich von früheren Arbeiten an Systemen durch Verwendung Zusammenfassung Algebra Informationssysteme zu beschreiben und nicht Differentialrechnung Materialsysteme beschreiben.^[2] Die Theorie des Finite-State-Wandlers wurde unter verschiedenen Namen von verschiedenen Forschungsgemeinschaften entwickelt.^[3] Das frühere Konzept von Turing -Maschinen wurden auch in der Disziplin zusammen mit neuen Formen von unendlich-staatlichen Automaten enthalten, wie z. Pushdown -Automaten.

1956 sah die Veröffentlichung von Automatenstudien, die Arbeit von Wissenschaftlern sammelte, einschließlich Claude Shannon, W. Ross Ashby, John von Neumann, Marvin Minsky, Edward F. Moore, und Stephen Cole Kleene.^[4] Mit der Veröffentlichung dieses Bandes "wurde die Automatentheorie als relativ autonome Disziplin".^[5] Das Buch enthielt Kleenes Beschreibung der regulären Ereignisse oder reguläre Sprachenund ein relativ stabiles Maß für die Komplexität in Turing -Maschinenprogrammen von Shannon.^[6] Im selben Jahr, Noam Chomsky beschrieben die Chomsky -Hierarchie, eine Korrespondenz zwischen Automaten und formelle Grammatiken,^[7] und Ross Ashby veröffentlicht Eine Einführung in die Kybernetik, ein zugängliches Lehrbuch, das Automata und Informationen unter Verwendung der grundlegenden Set -Theorie erläutert.

Die Untersuchung der linearen Automaten^[angeben] führte zur Myhill-Nerode-Theorem,^[8] Dies gibt einen notwendigen und ausreichenden Zustand, damit eine formale Sprache regelmäßig ist, und eine genaue Anzahl der Zustände in einer minimalen Maschine für die Sprache. Das Lemma für reguläre Sprachen pumpen, auch nützlich in Regelmäßigkeitsergebnissen, wurde in dieser Zeit von nachgewiesen Michael O. Rabin und Dana Scottzusammen mit der rechnerischen Äquivalenz deterministischer und nicht deterministischer endlicher Automata.^[9]

In den 1960er Jahren tauchte eine Reihe algebraischer Ergebnisse, die als "Strukturtheorie" oder "algebraische Zersetzungstheorie" bekannt sind, die sich mit der Realisierung von sequentiellen Maschinen aus kleineren Maschinen durch Zusammenhänge befasste.^[10] Während jeder endliche Automat mit a simuliert werden kann Universal Gate SetDies erfordert, dass die Simulationsschaltung Schleifen der willkürlichen Komplexität enthält. Die Strukturtheorie befasst sich mit der "schleifenfreien" Realisierbarkeit von Maschinen.^[5] Die Theorie von Rechenkomplexität nahm auch in den 1960er Jahren Gestalt an.^[11][12] Am Ende des Jahrzehnts wurde die Automatentheorie als "die reine Mathematik der Informatik" angesehen.^[5]

Automaten

Was folgt, ist eine allgemeine Definition von Automaton, die eine breitere Definition von beschränkt System zu einem als in diskreten Zeitschritten wirkenden angesehen, wobei sein Zustandsverhalten und die Ausgaben in jedem Schritt durch unveränderliche Funktionen nur seines Zustands und seiner Eingabe definiert werden.^[5]

Informelle Beschreibung

Ein Automat läuft Wenn es eine Sequenz von gegeben ist Eingänge in diskreter (individueller) Zeitschritte oder Schritte. Ein Automaten verarbeitet eine Eingabe, die aus einem Satz von ausgewählt wurde Symbole oder Briefe, was als als genannt wird Eingang Alphabet. Die vom Automaten als Eingabe in jedem Schritt empfangenen Symbole sind eine Abfolge von Symbolen, die genannt werden Wörter. Ein Automat hat einen Satz von Zustände. In jedem Moment während eines Automatons ist der Automaton in einer seiner Staaten. Wenn der Automaton eine neue Eingabe erhält, wechselt er in einen anderen Zustand (oder Übergänge) basierend auf a Übergangsfunktion Das nimmt das vorherige Status und das aktuelle Eingangssymbol als Parameter an. Gleichzeitig nannte eine andere Funktion die Ausgangsfunktion erzeugt Symbole aus dem Alphabet ausgebenauch nach dem vorherigen Zustand und dem aktuellen Eingangssymbol. Der Automaten liest die Symbole des Eingangsworts und der Übergänge zwischen den Zuständen, bis das Wort vollständig gelesen wird, wenn es endlich länger ist, an welchem ​​Punkt der Automaton Halt. Ein Zustand, in dem der Automaton anhält Endzustand.

Um die möglichen Status-/Eingangs-/Ausgangssequenzen in einem Automat zu untersuchen formelle Sprache Theorie kann eine Maschine a zugewiesen werden a Startzustand und ein Satz von Staaten akzeptieren. Dann, je nachdem, ob ein Lauf aus dem Startzustand in einem akzeptierenden Zustand endet, kann der Automat gesagt werden annehmen oder ablehnen eine Eingangssequenz. Die Menge aller von einem Automat akzeptierten Wörter wird als die genannt vom Automaten erkannte Sprache. Ein vertrautes Beispiel für eine Maschine, die eine Sprache erkennt, ist eine elektronisches Schloss Dies akzeptiert oder ablehnt Versuche, den richtigen Code einzugeben.

Formale Definition

Automat

Ein Automat kann formell durch a dargestellt werden 5-Tupel ${\ displayStyle m = \ Langle \ sigma, \ gamma, q, \ delta, \ lambda \ rangle}$, wo:

• ${\ displayStyle \ sigma}$ ist ein endlicher Satz von Symbole, genannt Alphabet eingeben des Automatens,
• ${\ displayStyle \ gamma}$ ist ein weiterer endlicher Satz von Symbolen, genannt die Alphabet ausgeben des Automatens,
• ${\ displayStyle q}$ ist ein Satz von Zustände,
• ${\ displayStyle \ Delta}$ ist der NÄCHSTE EINFAKTIERUNG oder Übergangsfunktion ${\ displayStyle \ delta: q \ times \ sigma \ bis q}$ Mapping-State-Input-Paare für Nachfolgerzustände,
• ${\ displayStyle \ lambda}$ ist der Nächste Funktion ${\ displaystyle \ lambda: q \ times \ sigma \ to \ gamma}$ Mapping Status-Input-Paare für Ausgänge.

Wenn ${\ displayStyle q}$ ist dann endlich ${\ displayStyle m}$ ist ein Finite Automaton.^[5]

Eingabewort

Ein Automaten liest ein Finitie Saite von Symbolen ${\ displayStyle a_ {1} a_ {2} ... a_ {n}}$, wo ${\ displayStyle a_ {i} \ in \ sigma}$, was als als genannt wird Eingabewort. Die Menge aller Wörter wird durch gekennzeichnet ${\ displaystyle \ sigma ^{*}}$.

Laufen

Eine Reihenfolge von Zuständen ${\ displayStyle q_ {0}, q_ {1}, ... q_ {n}}$, wo ${\ displayStyle q_ {i} \ in q}$ so dass ${\ displayStyle q_ {i} = \ delta (q_ {i-1}, a_ {i})}$ zum ${\ displayStyle 0 <i \ leq n}$, ist ein Lauf des Automatons auf einem Eingang ${\ displayStyle a_ {1} a_ {2} ... a_ {n} \ in \ sigma ^{*}}$ Ausgehend von Staat ${\ displayStyle q_ {0}}$. Mit anderen Worten, zunächst ist der Automat am Startzustand ${\ displayStyle q_ {0}}$und erhält Eingaben ${\ displayStyle a_ {1}}$. Zum ${\ displayStyle a_ {1}}$ und jede Anhängerschaft ${\ displayStyle a_ {i}}$ In der Eingangszeichenfolge wählt der Automat den nächsten Status aus ${\ displayStyle q_ {i}}$ gemäß der Übergangsfunktion ${\ displayStyle \ delta (q_ {i-1}, a_ {i})}$, bis zum letzten Symbol ${\ displayStyle a_ {n}}$ wurde gelesen und die Maschine in der verlassen Endzustand des Laufs, ${\ displayStyle q_ {n}}$. In ähnlicher Weise emittiert der Automaton in jedem Schritt ein Ausgangssymbol gemäß der Ausgangsfunktion ${\ displayStyle \ lambda (q_ {i-1}, a_ {i})}$.

Die Übergangsfunktion ${\ displayStyle \ Delta}$ wird induktiv erweitert in ${\ displaystyle {\ overline {\ delta}}: q \ times \ sigma ^{*} \ to q}$ Um das Verhalten der Maschine zu beschreiben, wenn sie ganze Eingangswörter gefüttert haben. Für die leere Zeichenfolge ${\ displayStyle \ varepsilon}$, ${\ displayStyle {\ overline {\ delta}} (q, \ varepsilon) = q}$ Für alle Staaten ${\ displayStyle q}$und für Saiten ${\ displayStyle wa}$ wo ${\ displayStyle a}$ ist das letzte Symbol und ${\ displayStyle W}$ ist der (möglicherweise leere) Rest der Zeichenfolge, $oder$.^[10] Die Ausgangsfunktion ${\ displayStyle \ lambda}$ kann ähnlich erweitert werden in ${\ displayStyle {\ overline {\ lambda}} (q, w)}$, was die vollständige Ausgabe der Maschine beim Ausführen von Word verleiht ${\ displayStyle W}$ vom Staat ${\ displayStyle q}$.

Akzeptor

Um einen Automat mit der Theorie von zu studieren formelle Sprachen, ein Automat kann als als betrachtet werden AkzeptorErsetzen des Ausgangsalphabets und der Funktion ${\ displayStyle \ gamma}$ und ${\ displayStyle \ lambda}$ mit

• ${\ displayStyle q_ {0} \ in q}$, ein bestimmtes Staat starten, und
• ${\ displayStyle f}$, eine Reihe von Zuständen von ${\ displayStyle q}$ (d.h. ${\ displayStyle f \ subseteq q}$) genannt Staaten akzeptieren.

Dies ermöglicht die Definition:

Wort akzeptieren

Ein Wort ${\ displayStyle w = a_ {1} a_ {2} ... a_ {n} \ in \ sigma ^{*}}$ ist ein Wort akzeptieren für den Automat, wenn ${\ displaystyle {\ overline {\ delta}} (q_ {0}, w) \ in f}$Das heißt, wenn nach dem Verzehr der gesamten Saite ${\ displayStyle W}$ Die Maschine befindet sich in einem Akzeptieren.

Anerkannte Sprache

Die Sprache ${\ displayStyle l \ subseteq \ sigma ^{*}}$ anerkannt von einem Automat ist der Satz aller Wörter, die vom Automaten akzeptiert werden. $oder$.^[13]

Erkennbare Sprachen

Das erkennbare Sprachen sind die Sprachen, die von einem Automaten erkannt werden. Zum Finite Automaten Die erkennbaren Sprachen sind reguläre Sprachen. Für verschiedene Arten von Automata sind die erkennbaren Sprachen unterschiedlich.

Variantendefinitionen von Automata

Automaten werden definiert, um nützliche Maschinen im mathematischen Formalismus zu untersuchen. Die Definition eines Automatens ist also für Variationen gemäß der "realen Weltmaschine" offen, die wir mit dem Automat modellieren möchten. Die Menschen haben viele Variationen von Automaten untersucht. Im Folgenden sind einige beliebte Variationen in der Definition verschiedener Komponenten der Automata aufgeführt.

Eingang

• Endliche Eingabe: Ein Automat, der nur eine endliche Abfolge von Symbolen akzeptiert. Die obige Einführungsdefinition umfasst nur endliche Wörter.
• Unendlicher Eingang: Ein Automat, der unendliche Wörter akzeptiert (ω-Wörter). Solche Automaten werden genannt ω-automata.
• Baumworteingabe: Die Eingabe kann a sein Baum der Symbole anstelle von Sequenz von Symbolen. In diesem Fall nach dem Lesen jedes Symbols der Automaton liest Alle Nachfolgersymbole im Eingabebaum. Es wird gesagt, dass der Automaten macht eine Kopie Für jeden Nachfolger und jede solche Kopie beginnt auf einem der Nachfolgersymbole aus dem Staat gemäß der Übergangsbeziehung des Automatiks zu laufen. Ein solcher Automaten heißt a Baumautomaton.
• Infinite Baumeingabe: Die beiden oben genannten Erweiterungen können kombiniert werden, sodass der Automat eine Baumstruktur mit (in) endlichen Zweigen liest. Ein solcher Automaten wird als eine genannt Unendlicher Baumautomaton.

Zustände

• Einzelstaat: Ein Automat mit einem Zustand, auch a genannt Kombinationsschaltungführt eine Transformation durch, die implementiert werden kann Kombinationslogik.^[10]
• Endliche Zustände: Ein Automat, der nur eine begrenzte Anzahl von Zuständen enthält.
• Unendliche Zustände: Ein Automaten, der möglicherweise keine begrenzte Anzahl von Staaten hat, oder sogar a zählbar Anzahl der Zustände. Verschiedene Arten des abstrakten Gedächtnisses können verwendet werden, um solche Maschinen endliche Beschreibungen zu verleihen.
• Stapelspeicher: Ein Automat kann auch einen zusätzlichen Speicher in Form von a enthalten Stapel in welchen Symbolen gedrückt und geplagt werden können. Diese Art von Automat wird als als genannt Pushdown -Automaten.
• Wartespeicher: Ein Automaten kann Speicher in Form von a haben Warteschlange. Eine solche Maschine heißt Warteschlangenmaschine und ist Turing-Complete.
• Bandspeicher: Die Ein- und Ausgänge von Automaten werden häufig als Eingang und Ausgabe beschrieben Bänder. Einige Maschinen haben zusätzliche Arbeitsbänder, einschließlich der Turing Maschine, linear begrenzter Automaten, und Protokoll-Raum-Wandler.

Übergangsfunktion

• Deterministisch: Für einen bestimmten aktuellen Zustand und ein Eingabetriebsymbol, wenn ein Automat nur zu einem und nur zu einem Zustand springen kann, dann ist es a deterministischer Automaten.
• Nichtdeterministisch: Ein Automat, der nach dem Lesen eines Eingabensymbols in eine Reihe von Zuständen springen kann, wie sie durch seine Übergangsbeziehung lizenziert wird. Beachten Sie, dass die Laufzeitübergangsfunktion durch Übergangsbeziehung ersetzt wird: der Automaton nicht deterministisch Beschließt, in eine der erlaubten Entscheidungen zu springen. Solche Automaten werden genannt Nichtdeterministische Automaten.
• Wechsel: Diese Idee ist dem Baumautomaton, aber orthogonal. Der Automaten kann seine leiten Mehrere Kopien auf der gleich Als nächstes lesen Sie Symbol. Solche Automaten werden genannt Wechselautomaten. Akzeptanzbedingung muss alle Läufe von solchen erfüllen Kopien die Eingabe akzeptieren.

Akzeptanzbedingung

• Akzeptanz endlicher Wörter: Wie in der obigen informellen Definition beschrieben.
• Akzeptanz unendlicher Wörter: ein Omega Automaton Kann nicht endgültige Zustände haben, da unendliche Wörter niemals enden. Die Akzeptanz des Wortes wird vielmehr durch Betrachtung der unendlichen Sequenz der besuchten Zustände während des Laufs entschieden.
• Probabilistische Akzeptanz: Ein Automaten muss eine Eingabe nicht strikt akzeptieren oder ablehnen. Es kann die Eingabe mit einigen akzeptieren Wahrscheinlichkeit zwischen Null und einem. Zum Beispiel Quantenfinite -Automaten, Geometrischer Automaten und Metrikautomaton probabilistische Akzeptanz haben.

Verschiedene Kombinationen der oben genannten Variationen erzeugen viele Automatenklassen.

Die Automatentheorie ist ein Gegenstand, der Eigenschaften verschiedener Arten von Automaten untersucht. Beispielsweise werden die folgenden Fragen zu einer bestimmten Art von Automata untersucht.

• Welche Klasse von formalen Sprachen ist für eine Art von Automata erkennbar? (Erkennbare Sprachen)
• Sind bestimmte Automaten abgeschlossen Unter Union, Kreuzung oder Ergänzung formaler Sprachen? (Verschlusseigenschaften)
• Wie ausdrucksstark ist eine Art von Automaten in Bezug auf die Erkennung einer Klasse formeller Sprachen? Und ihre relative Ausdruckskraft? (Sprachhierarchie)

Die Automatenheorie untersucht auch die Existenz oder Nichtdage von keiner effektive Algorithmen Um Probleme zu lösen, die der folgenden Liste ähneln:

• Akzeptiert ein Automaten ein Eingabebuch? (Leeresprüfung)
• Ist es möglich, einen bestimmten nicht deterministischen Automat in deterministische Automaten zu verwandeln, ohne die erkennbare Sprache zu ändern? (Bestimmung)
• Was ist für eine bestimmte formale Sprache der kleinste Automat, der sie erkennt? (Minimierung)

Arten von Automaten

Das Folgende ist eine unvollständige Liste von Automatenarten.

Diskrete, kontinuierliche und hybride Automaten

Normalerweise beschreibt Automata -Theorie die Zustände abstrakter Maschinen, aber es gibt diskrete Automaten. Analoge Automaten oder kontinuierliche Automaten oder Hybrid diskrete kontinuierliche Automaten, die digitale Daten, analoge Daten oder kontinuierliche Zeit oder digitale bzw. analoge Daten verwenden.

Hierarchie in Bezug auf Befugnisse

Das Folgende ist eine unvollständige Hierarchie in Bezug auf die Befugnisse verschiedener Arten von virtuellen Maschinen. Die Hierarchie spiegelt die verschachtelten Kategorien von Sprachen wider, die die Maschinen akzeptieren können.^[14]

Anwendungen

Jedes Modell in der Automatentheorie spielt eine wichtige Rolle in mehreren angewandten Bereichen. Finite Automaten werden in Textverarbeitung, Compilern und Hardwaredesign verwendet. Kontextfreie Grammatik (CFGs) werden in Programmiersprachen und künstlicher Intelligenz verwendet. Ursprünglich wurden CFGs in der Untersuchung der menschlichen Sprachen verwendet. Mobilfunk Automaten werden im Bereich von verwendet künstliches Leben, das berühmteste Beispiel ist John Conway's Spiel des Lebens. Einige andere Beispiele, die mit der Automatentheorie in der Biologie erklärt werden konnten, sind Wachstums- und Pigmentierungsmuster von Mollusk- und Kiefernkegeln. Eine Theorie, die darauf hindeutet, dass das gesamte Universum von einer Art diskreter Automat berechnet wird, wird von einigen Wissenschaftlern befürwortet. Die Idee entstand aus der Arbeit von Konrad Zuseund wurde in Amerika von populär gemacht von Edward Fredkin. Automaten erscheinen auch in der Theorie endlicher Felder: der Reihe von irreduziblen Polynomen, die als Zusammensetzung des Grades zwei Polynome geschrieben werden können, ist in der Tat eine reguläre Sprache.^[15] Ein weiteres Problem, für das Automata verwendet werden kann, ist die Induktion regulärer Sprachen.

Automaten -Simulatoren

Automata -Simulatoren sind pädagogische Tools, mit denen Automatentheorie unterrichtet, gelernt und erforscht wird. Ein Automaten -Simulator nimmt die Beschreibung eines Automatens als Eingabe ein und simuliert dann seine Arbeit für eine beliebige Eingangszeichenfolge. Die Beschreibung des Automatens kann auf verschiedene Weise eingegeben werden. Ein Automat kann in a definiert werden Symbolische Sprache oder seine Spezifikation kann in einer vorgefertigten Form eingegeben werden oder sein Übergangsdiagramm kann durch Klicken und Ziehen der Maus gezeichnet werden. Zu den bekannten Automaten -Simulatoren zählen Turings World, JFLAP, VAS, Tags und Simstudio.^[16]

Verbindung zur Kategorie -Theorie

Man kann mehrere unterschiedliche definieren Kategorien von Automaten^[17] Nach der Automata -Klassifizierung in verschiedene im vorherige Abschnitt beschriebene Typen. Die mathematische Kategorie deterministischer Automaten, sequentielle Maschinen oder Sequentielle Automatenund Turing -Maschinen mit Automaten -Homomorphismen, die die Pfeile zwischen Automaten definieren, ist a Kartesische Kategorie geschlossen,^[18][19] Es hat sowohl kategoriale Grenzen als auch Colimits. Ein Automaten -Homomorphismus kartiert eine Fülle eines Automatens A_i auf die Fülle eines anderen Automatens A_j.^[20] Automaten -Homomorphismen können auch als als betrachtet werden Automaten -Transformationen oder als Semigroup -Homomorphismen, wenn der Staatsraum, Sdes Automatons wird als Semigroup definiert S_g. Monoide werden auch als geeignete Einstellung für Automaten in betrachtet Monoidale Kategorien.^[21][22][23]

Kategorien variabler Automata

Man könnte auch a definieren Variabler Automaten, im Sinne von Norbert Wiener in seinem Buch über Der menschliche Gebrauch von Menschen über Die Endomorphismen ${\ displayStyle a_ {i} \ to a_ {i}}$. Dann kann man zeigen, dass solche variablen Automaten -Homomorphismen eine mathematische Gruppe bilden. Bei nicht deterministischen oder anderen komplexen Art von Automaten kann der letztere Satz von Endomorphismen jedoch zu einem werden Variabler Automaten Gruppoid. Daher sind Kategorien variabler Automata jeglicher Art Kategorien von Gruppenkategorien oder Gruppenkategorien. Darüber hinaus ist die Kategorie der reversiblen Automaten dann a2 Kategorieund auch eine Unterkategorie der 2-Kategorie von Gruppenoiden oder der Gruppenkategorie.

Siehe auch

• Boolesche Differenzkalkül

Verweise

Weitere Lektüre

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2000). Einführung in die Automatentheorie, Sprachen und Berechnung (2. Aufl.). Pearson Ausbildung. ISBN 978-0-201-44124-6.{{}}: CS1 Wartung: Verwendet Autorenparameter (Link)
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 978-0-534-94728-6. Teil eins: Automaten und Sprachen, Kapitel 1–2, S. 29–122. Abschnitt 4.1: Langlebige Sprachen, S. 152–159. Abschnitt 5.1: Unentscheidbare Probleme aus der Sprachtheorie, S. 172–183.
• Elaine Rich (2008). Automaten, Berechnbarkeit und Komplexität: Theorie und Anwendungen. Pearson. ISBN 978-0-13-228806-4.
• Salomaa, Arto (1985). Berechnung und Automaten. Enzyklopädie der Mathematik und ihrer Anwendungen. Vol. 25. Cambridge University Press. ISBN 978-0-521-30245-6. Zbl 0565.68046.
• Anderson, James A. (2006). Automatenheorie mit modernen Anwendungen. Mit Beiträgen von Tom Head. Cambridge: Cambridge University Press. ISBN 978-0-521-61324-8. Zbl 1127.68049.
• Conway, J.H. (1971). Reguläre Algebra und endliche Maschinen. Chapman and Hall Mathematics Series. London: Chapman & Hall. Zbl 0231.94041.
• John M. Howie (1991) Automaten und Sprachen, Clarendon Press ISBN0-19-853424-8 HERR 1254435
• Sakarovitch, Jacques (2009). Elemente der Automata -Theorie. Übersetzt aus den Franzosen von Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
• James P. Schmeiser, David T. Barnard (1995). Erstellen eines Top-Down-Parse-Bestellungs mit Bottom-up-Parsen. Elsevier North-Holland.{{}}: CS1 Wartung: Verwendet Autorenparameter (Link)
• Igor Aleksander, F.Keith Hanna (1975). Automatenheorie: Ein technischer Ansatz.New York: Crane Russak. ISBN 978-0-8448-0657-0.{{}}: CS1 Wartung: Verwendet Autorenparameter (Link)
• Marvin Minsky (1967). Berechnung: endliche und unendliche Maschinen.Princeton, N.J.: Prentice Hall.
• John C. Martin (2011). Einführung in die Sprachen und die Theorie der Berechnung. New York: McGraw Hill. ISBN 978-0-07-319146-1.

Externe Links

• dk.brics.automaton
• libfa