Automaten und formale Sprachen
Die Theorie der Automaten und formalen Sprachen untersucht idealisierte Maschinen mit zunehmender Leistungsfähigkeit und die Klassen von Zeichenketten oder Sprachen, die jede erkennen kann. Sie liefert eine präzise mathematische Beschreibung dessen, was als Muster gilt und was zu dessen Erkennung erforderlich ist.
Definition
Eine formale Sprache ist eine Menge endlicher Zeichenketten über einem festen Alphabet, und ein Automat ist ein abstraktes Rechengerät, dessen akzeptierende Berechnungen eine solche Sprache definieren; der Bereich klassifiziert Sprachen nach der einfachsten Art von Automat oder Grammatik, die sie erzeugt oder erkennt.
Scope
Dieser Bereich umfasst endliche Automaten und reguläre Sprachen, Kellerautomaten und kontextfreie Sprachen, die Chomsky-Hierarchie, die Grammatiken mit Maschinenmodellen in Beziehung setzt, Abschluss- und Entscheidungseigenschaften von Sprachklassen sowie Automaten, die unendliche Wörter und Bäume verarbeiten, zusammen mit den dazugehörigen algebraischen und logischen Charakterisierungen.
Sub-topics
Core questions
- Welche Sprachen kann eine Maschine mit endlichem Speicher erkennen und welche nicht?
- Wie korrespondieren Grammatiken und Maschinenmodelle über die Ebenen der Chomsky-Hierarchie hinweg?
- Welche Fragen zu einer Sprachklasse, wie z. B. Leere oder Äquivalenz, sind algorithmisch entscheidbar?
- Wie erweitern sich Automaten auf unendliche Wörter und Bäume, und warum ist dies für die Verifikation wichtig?
Key theories
- Äquivalenz von deterministischen und nichtdeterministischen endlichen Automaten
- Jeder nichtdeterministische endliche Automat kann durch die Potenzmengenkonstruktion in einen deterministischen Automaten umgewandelt werden, der dieselbe Sprache akzeptiert, sodass Nichtdeterminismus auf der Ebene der endlichen Zustände keine zusätzliche Erkennungsleistung bietet, auch wenn er exponentiell prägnanter sein kann.
- Kleenes Satz
- Die von endlichen Automaten erkannten Sprachen sind genau die regulären Sprachen, die durch reguläre Ausdrücke beschrieben werden, wodurch die maschinelle, algebraische und grammatische Sichtweise der einfachsten Sprachklasse miteinander verbunden wird.
- Die Chomsky-Hierarchie
- Reguläre, kontextfreie, kontextsensitive und rekursiv aufzählbare Sprachen bilden eine strenge Inklusionskette, wobei jede Ebene einem Grammatiktyp und einem Automatenmodell mit entsprechender Speicherstruktur zugeordnet ist.
Clinical relevance
Endliche Automaten und reguläre Ausdrücke treiben die lexikalische Analyse in Compilern, die Textsuche und die Protokollspezifikation an, während kontextfreie Grammatiken die Grundlage für das Parsen von Programmiersprachen bilden; Automaten auf unendlichen Objekten bilden den algorithmischen Kern der Modellprüfung, bei der ein System anhand einer temporallogischen Spezifikation verifiziert wird.
History
Endliche Zustandsmodelle entstanden in den 1940er Jahren aus den neuronalen Netzen von McCulloch und Pitts und erhielten um 1951 von Kleene eine sprachtheoretische Form. Rabin und Scott führten 1959 nichtdeterministische Automaten ein, während Chomskys Grammatiken aus den späten 1950er Jahren Sprachklassen in die Hierarchie organisierten, die das Thema noch heute strukturiert.
Key figures
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Noam Chomsky
Related topics
Seminal works
- rabinScott1959
- sipser2013
- hopcroft2006
Frequently asked questions
- Warum kann ein endlicher Automat keine ausgeglichenen Klammern erkennen?
- Das Erkennen beliebig tiefer Verschachtelungen erfordert das Zählen, wie viele Öffnungen noch ungleich sind, was jede feste Anzahl von Zuständen überschreiten kann. Ein endlicher Automat hat nur einen begrenzten Speicher, sodass diese Zählfähigkeit eine Ebene höher liegt, bei Kellerautomaten und kontextfreien Sprachen.
- Was ist der praktische Nutzen der Theorie der formalen Sprachen?
- Sie zeigt Ingenieuren, welche Muster ein bestimmtes Werkzeug ausdrücken kann. Reguläre Ausdrücke reichen für Token aus, aber nicht für verschachtelte Strukturen, weshalb Compiler die Arbeit zwischen einem regulären Lexer und einem kontextfreien Parser aufteilen und warum Verifikationswerkzeuge auf Automaten über unendlichen Wörtern basieren.