In der theoretischen Informatik ist Automaten-Theorie die Studie von mathematischen Gegenständen genannt abstrakte Maschinen oder Automaten und die rechenbetonten Probleme, die mit ihnen gelöst werden können. Automaten kommen aus dem griechischen Wort  "selbsttätige" Bedeutung.

Die Zahl am Recht illustriert eine Zustandsmaschine, die einer wohl bekannter Vielfalt des Automaten gehört. Dieser Automat besteht aus Staaten (vertreten in der Zahl durch Kreise), und Übergänge (vertreten durch Pfeile). Da der Automat ein Symbol des Eingangs sieht, macht er einen Übergang (oder Sprung) zu einem anderen Staat, gemäß seiner Übergang-Funktion (der den aktuellen Staat und das neue Symbol als seine Eingänge nimmt).

Automaten-Theorie ist auch nah mit der formellen Sprachtheorie verbunden.

Ein Automat ist eine begrenzte Darstellung einer formellen Sprache, die ein unendlicher Satz sein kann.

Automaten werden häufig durch die Klasse von formellen Sprachen klassifiziert, die sie im Stande sind anzuerkennen.

Automaten spielen eine Hauptrolle in der Theorie der Berechnung, des Bearbeiter-Designs, grammatisch analysierend und der formellen Überprüfung.

Automaten

Folgender ist eine einleitende Definition eines Typs von Automaten, der versucht, einem Griff die wesentlichen an der Automaten-Theorie beteiligten Konzepte zu helfen.

Informelle Beschreibung

Ein Automat soll auf einer gegebenen Folge von Eingängen in Schritten der diskreten Zeit laufen. Jedes Mal Schritt, ein Automat bekommt Derjenige-Eingang, der von einer Reihe von Symbolen oder Briefen aufgenommen wird, der ein Alphabet genannt wird. Jederzeit haben die Symbole bis jetzt zum Automaten als Eingangsform eine begrenzte Folge von Symbolen gefressen, die ein Wort genannt wird. Ein Automat enthält einen begrenzten Satz von Staaten. An jedem Beispiel in der Zeit von etwas Lauf ist der Automat in einem seiner Staaten. Gehen Sie jedes Mal, wenn der Automat ein Symbol liest, springt er oder quert zu einem folgenden Staat durch, der durch eine Funktion entschieden wird, die aktuellen Staat und das als Rahmen zurzeit gelesene Symbol nimmt. Diese Funktion wird Übergang-Funktion genannt. Der Automat liest die Symbole des Eingangswortes nacheinander und quert vom Staat bis Staat gemäß der Übergang-Funktion durch, bis das Wort völlig gelesen wird. Sobald das Eingangswort gelesen worden ist, wie man sagt, ist der Automat angehalten worden und der Staat, an dem Automat angehalten hat, wird Endstaat genannt. Abhängig vom Endstaat wird es gesagt, dass der Automat entweder akzeptiert oder ein Eingangswort zurückweist. Es gibt eine Teilmenge von Staaten des Automaten, der als der Satz definiert wird, Staaten zu akzeptieren. Wenn der Endstaat ein akzeptierender Staat ist, dann akzeptiert der Automat das Wort. Sonst wird das Wort zurückgewiesen. Der Satz aller durch einen Automaten akzeptierten Wörter wird die durch den Automaten anerkannte Sprache genannt.

Kurz gesagt, ein Automat ist ein mathematischer Gegenstand, der ein Wort als Eingang nimmt und sich dafür entscheidet, entweder es zu akzeptieren oder ihn zurückzuweisen. Da alle rechenbetonten Probleme in die akzeptieren/zurückweisen Frage auf Wörtern reduzierbar sind (alle Problem-Beispiele können in einer begrenzten Länge von Symbolen vertreten werden),

Automaten-Theorie spielt eine entscheidende Rolle in der rechenbetonten Theorie.

Formelle Definition

Automat

:An-Automat wird formell durch einen 5-Tupel-(Q, Σ,δ, q, F), wo vertreten:

:*Q ist ein begrenzter Satz von Staaten.

:*Σ ist ein begrenzter Satz von Symbolen, genannt das Alphabet des Automaten.

:*δ ist die Übergang-Funktion, d. h. δ: Q × Σ  Q.

:*q ist der Anfang-Staat, d. h. der Staat des Automaten, bevor jeder Eingang, wo q  Q bearbeitet worden ist.

:*F ist eine Reihe von Staaten von Q (d. h. FQ) genannt akzeptieren Staaten.

Eingangswort

:An-Automat liest eine begrenzte Reihe von Symbolen a, a...., a, wo ein  Σ, der ein Eingangswort genannt wird. Der Satz aller Wörter wird durch Σ* angezeigt.

Geführter

Der:A-Lauf des Automaten auf einem Eingangswort w = a, a...., ein  Σ *, ist eine Folge von Staaten q, q, q...., q, wo q  Q solch, dass q der Anfang-Staat und q = δ (q, a) für 0, und dann der Automat ist, Symbole des Eingangswortes in der Folge liest. Wenn der Automat Symbol liest, springt es, um q = δ (q, a) festzusetzen. wie man sagt, ist q der Endstaat des Laufs.

Das Annehmen des Wortes

:A-Wort w  Σ* wird durch den Automaten wenn q  F akzeptiert.

Anerkannte Sprache

:An-Automat kann eine formelle Sprache anerkennen. Die Sprache L  Σ* anerkannt durch einen Automaten ist der Satz aller Wörter, die durch den Automaten akzeptiert werden.

Erkennbare Sprachen

Erkennbare Sprachen von:The sind der Satz von Sprachen, die durch einen Automaten anerkannt werden. Für die obengenannte Definition von Automaten sind die erkennbaren Sprachen regelmäßige Sprachen. Für verschiedene Definitionen von Automaten sind die erkennbaren Sprachen verschieden.

Verschiedene Definitionen von Automaten

Automaten werden definiert, um nützliche Maschinen unter dem mathematischen Formalismus zu studieren. Also, die Definition eines Automaten ist für Schwankungen gemäß der "echten Weltmaschine" offen, die wir zum Modell mit dem Automaten wollen. Leute haben viele Schwankungen von Automaten studiert. Die am meisten normale Variante, die oben beschrieben wird, wird einen deterministischen begrenzten Automaten genannt. Der folgende ist einige populäre Schwankungen in der Definition von verschiedenen Bestandteilen von Automaten.

Eingang

• Begrenzter Eingang: Ein Automat, der nur begrenzte Folge von Symbolen akzeptiert. Die obengenannte einleitende Definition umfasst nur begrenzte Wörter.
• Unendlicher Eingang: Ein Automat, der unendliche Wörter (ω-words) akzeptiert. Solche Automaten werden ω-automata genannt.
• Baumwort hat eingegeben: Der Eingang kann ein Baum von Symbolen statt der Folge von Symbolen sein. In diesem Fall nach dem Lesen jedes Symbols liest der Automat alle Nachfolger-Symbole im Eingangsbaum. Es wird gesagt, dass der Automat eine Kopie von sich für jeden Nachfolger macht und jede solche Kopie anfängt, auf einem des Nachfolger-Symbols vom Staat gemäß der Übergang-Beziehung des Automaten zu laufen. Solch ein Automat wird Baumautomaten genannt.
• Unendlicher Baum hat eingegeben: Die zwei Erweiterungen können oben verbunden werden, so liest der Automat eine Baumstruktur mit (in) begrenzten Zweigen. Solch ein Automat wird unendlichen Baumautomaten genannt

Staaten

• Endzustände: Ein Automat, der nur eine begrenzte Zahl von Staaten enthält. Die obengenannte einleitende Definition beschreibt Automaten mit begrenzten Zahlen von Staaten.
• Unendliche Staaten: Ein Automat, der keine begrenzte Zahl von Staaten oder sogar eine zählbare Zahl von Staaten haben kann. Zum Beispiel hat das Quant begrenzter Automat oder topologischer Automat unzählbare Unendlichkeit von Staaten.
• Stapel-Gedächtnis: Ein Automat kann auch etwas Extragedächtnis in der Form eines Stapels enthalten, in dem Symbole gestoßen und knallen gelassen werden können. Diese Art des Automaten wird einen pushdown Automaten genannt

Übergang-Funktion

• Deterministisch: Für einen gegebenen aktuellen Staat und ein Eingangssymbol, wenn ein Automat nur zu einem und nur einem Staat dann springen kann, ist es ein deterministischer Automat.
• Nichtdeterministisch: Ein Automat, dass, nach dem Lesen eines Eingangssymbols, in einigen mehrerer Staaten, wie lizenziert, durch seine Übergang-Beziehung springen kann. Bemerken Sie, dass die Begriff-Übergang-Funktion durch die Übergang-Beziehung ersetzt wird: Der Automat entscheidet sich nichtdeterministisch dafür, in eine der erlaubten Wahlen zu springen. Solche Automaten werden nichtdeterministische Automaten genannt.
• Wechsel: Diese Idee ist dem Baumautomaten ziemlich ähnlich, aber orthogonal. Der Automat kann seine vielfachen Kopien auf demselben folgenden gelesenen Symbol führen. Solche Automaten werden Wechselautomaten genannt. Annahmebedingung muss alle Läufe solcher Kopien befriedigen, um den Eingang zu akzeptieren.

Annahmebedingung

• Annahme von begrenzten Wörtern: Dasselbe, wie beschrieben, in der informellen Definition oben.
• Annahme von unendlichen Wörtern: Ein Omega-Automat kann Endstaaten nicht haben, weil unendliche Wörter nie enden. Eher wird die Annahme des Wortes durch das Schauen auf die unendliche Folge von besuchten Staaten während des Laufs entschieden.
• Annahme von Probabilistic: Ein Automat braucht nicht ausschließlich zu akzeptieren oder einen Eingang zurückzuweisen. Es kann den Eingang mit etwas Wahrscheinlichkeit zwischen der Null und ein akzeptieren. Zum Beispiel hat Quant begrenzter Automat, geometrischer Automat und metrischer Automat probabilistic Annahme.

Verschiedene Kombinationen der obengenannten Schwankungen erzeugen viele Klassen des Automaten.

Automaten-Theorie

Automaten-Theorie ist ein Gegenstand, der Eigenschaften von verschiedenen Typen von Automaten studiert. Zum Beispiel werden die folgenden Fragen über einen gegebenen Typ von Automaten studiert.

• Welche Klasse von formellen Sprachen ist durch einen Typ von Automaten erkennbar? (Erkennbare Sprachen)
• Werden bestimmte Automaten unter der Vereinigung, Kreuzung oder Fertigstellung von formellen Sprachen geschlossen? (Verschluss-Eigenschaften)
• Wie viel ist ein Typ von Automaten ausdrucksvoll, in Bezug auf Klasse von formellen Sprachen anzuerkennen? Und, ihre ausdrucksvolle Verhältnismacht? (Sprachhierarchie)

Automaten-Theorie studiert auch, wenn dort ein wirksamer Algorithmus bestehen oder der folgenden Liste ähnliche Probleme nicht zu beheben.

• Akzeptiert ein Automat ein Eingangswort? (Leere-Überprüfung)

Ist

• es möglich, einen gegebenen nichtdeterministischen Automaten in den deterministischen Automaten umzugestalten, ohne die erkennbare Sprache zu ändern? (Determinization)
• Für eine gegebene formelle Sprache, wie ist der kleinste Automat, der erkennt es an? (Minimierung).

Klassen von Automaten

Der folgende ist eine unvollständige Liste von Typen von Automaten.

Getrennte, dauernde und hybride Automaten

Normalerweise beschreibt Automaten-Theorie die Staaten von abstrakten Maschinen, aber es gibt analoge Automaten oder dauernde Automaten oder hybride getrennt-dauernde Automaten, die analoge Daten, dauernde Zeit oder beide verwenden.

Anwendungen

Jedes Modell in der Automaten-Theorie spielt imporant Rollen in mehreren angewandten Gebieten. Begrenzte Automaten werden in der Textverarbeitung, den Bearbeitern und dem Hardware-Design verwendet. Grammatik ohne Zusammenhänge (CFGs) wird auf Programmiersprachen und künstlicher Intelligenz verwendet. Ursprünglich wurden CFGs in der Studie der menschlichen Sprachen verwendet. Zellautomaten werden im Feld der Biologie, das allgemeinste Beispiel verwendet, das das Spiel von John Conway des Lebens ist. Einige andere Beispiele, die mit der Automaten-Theorie in der Biologie erklärt werden konnten, schließen Weichtier und Kiefernzapfen-Wachstum und Pigmentationsmuster ein. Weiter gehend, wird eine Theorie, die darauf hinweist, dass das ganze Weltall durch eine Art ein getrennter Automat geschätzt wird, von einigen Wissenschaftlern verteidigt. Die Idee, die in der Arbeit von Konrad Zuse hervorgebracht ist, und wurde in Amerika von Edward Fredkin verbreitet.

Automaten-Simulatoren

Automaten-Simulatoren sind pädagogische Werkzeuge, die verwendet sind, um Automaten-Theorie zu unterrichten, zu erfahren und zu erforschen. Ein Automaten-Simulator nimmt als Eingang die Beschreibung eines Automaten und täuscht dann sein Arbeiten für eine willkürliche Eingangsschnur vor. In die Beschreibung des Automaten kann auf mehrere Weisen eingegangen werden. Ein Automat kann auf einer symbolischen Sprache definiert werden, oder in seine Spezifizierung kann in einer vorbestimmten Form eingegangen werden, oder sein Übergang-Diagramm kann gezogen werden, indem es die Maus geklickt und gezogen wird. Weithin bekannte Automaten-Simulatoren schließen die Welt von Turing, JFLAP, VAS, ANHÄNGSEL und SimStudio ein.

Verbindung zur Kategorie-Theorie

Man kann mehrere verschiedene Kategorien von Automaten im Anschluss an die Automaten-Klassifikation in verschiedene in der vorherigen Abteilung beschriebene Typen definieren. Die mathematische Kategorie von deterministischen Automaten, folgenden Maschinen oder folgenden Automaten und Maschinen von Turing mit dem Automaten-Homomorphismus, der die Pfeile zwischen Automaten definiert, ist eine Kartesianische geschlossene Kategorie, sie hat sowohl kategorische Grenzen als auch colimits. Ein Automaten-Homomorphismus stellt einen fünffachen von einem Automaten auf den fünffachen von einem anderen Automaten kartografisch dar

A. Automaten-Homomorphismus kann auch als Automaten-Transformationen oder als Halbgruppenhomomorphismus betrachtet werden, wenn der Zustandraum, S, des Automaten als eine Halbgruppe definiert wird, wird S. Monoids auch als eine passende Einstellung für Automaten in monoidal Kategorien betrachtet.

Kategorien von variablen Automaten

Man konnte auch einen variablen Automaten, in im Sinne Norbert Wieners in seinem Buch auf dem "menschlichen Gebrauch von Menschen" über die Endomorphismen-> A definieren. Dann kann man zeigen, dass solcher variabler Automaten-Homomorphismus eine mathematische Gruppe bildet. Im Fall von nichtdeterministischen oder anderen komplizierten Arten von Automaten kann der letzte Satz von Endomorphismen, jedoch, ein variabler Automat groupoid werden. Deshalb, im allgemeinsten Fall, sind Kategorien von variablen Automaten jeder Art Kategorien von groupoids oder groupoid Kategorien. Außerdem ist die Kategorie von umkehrbaren Automaten dann ein

2-Kategorien-, und auch eine Unterkategorie des 2-Kategorien-von groupoids oder der groupoid Kategorie.

• Teil Ein: Automaten und Sprachen, Kapitel 1-2, Seiten 29-122. Abschnitt 4.1: Entscheidbare Sprachen, Seiten 152-159. Abschnitt 5.1: Unentscheidbare Probleme aus der Sprachtheorie, Seiten 172-183.

Außenverbindungen

• Sehautomaten-Simulator, Ein Werkzeug für das Simulieren, Vergegenwärtigen und Umwandeln von Zustandsautomaten und Turing Maschinen, durch Jean Bovet
• JFLAP
• dk.brics.automaton
• libfa
• Proyecto SEPa (in Spanisch)
• Exorciser (in Deutsch)
• Automaten haben es auf Java mit den Quellen Gemacht, so können Sie sehen