Endliche Automaten und reguläre Sprachen

Endliche Automaten sind die einfachsten Rechenmaschinen, die Eingaben Symbol für Symbol unter Verwendung einer begrenzten Anzahl interner Zustände lesen, und die Sprachen, die sie erkennen, sind genau die regulären Sprachen.

Definition

Ein endlicher Automat ist eine Maschine mit einer endlichen Menge von Zuständen, einer Übergangsfunktion für Eingabesymbole, einem Startzustand und akzeptierenden Zuständen; er akzeptiert eine Zeichenkette, wenn das Lesen der Zeichenkette ihn vom Startzustand in einen akzeptierenden Zustand überführt, und die Menge der akzeptierten Zeichenketten ist seine Sprache.

Scope

Dieses Thema behandelt deterministische und nichtdeterministische endliche Automaten, ihre Äquivalenz mittels der Potenzmengenkonstruktion, reguläre Ausdrücke und den Satz von Kleene, den Satz von Myhill-Nerode und die Zustandsminimierung, Abschlusseigenschaften regulärer Sprachen sowie das Pumping-Lemma, das verwendet wird, um zu beweisen, dass bestimmte Sprachen nicht regulär sind.

Core questions

• Welche Sprachen können mit einer festen, endlichen Speichermenge erkannt werden?
• Warum sind deterministische und nichtdeterministische endliche Automaten gleich mächtig?
• Wie kann man beweisen, dass eine bestimmte Sprache nicht regulär ist?
• Was ist der kleinste Automat, der eine gegebene reguläre Sprache erkennt?

Key theories

Potenzmengenkonstruktion

Jeder nichtdeterministische endliche Automat kann durch einen deterministischen simuliert werden, dessen Zustände Mengen der ursprünglichen Zustände sind, was beweist, dass die beiden Modelle genau dieselben Sprachen erkennen.

Satz von Kleene

Eine Sprache wird von einem endlichen Automaten genau dann erkannt, wenn sie durch einen regulären Ausdruck beschrieben wird, was die Äquivalenz der maschinellen und algebraischen Beschreibungen regulärer Sprachen herstellt.

Satz von Myhill-Nerode

Eine Sprache ist genau dann regulär, wenn ihre Relation der Ununterscheidbarkeit von Zeichenketten endlich viele Klassen hat, und diese Klassen bestimmen den eindeutigen minimalen deterministischen Automaten für die Sprache.

Clinical relevance

Endliche Automaten sind die Grundlage für die Mustererkennung regulärer Ausdrücke, Scanner und lexikalische Analysatoren in Compilern, Suchen und Ersetzen in Texteditoren sowie die Mustererkennung in Netzwerkeinbruchsystemen, wo die Erkennung mit begrenztem Speicher die Verarbeitung schnell und vorhersehbar macht.

History

Aufbauend auf dem Modell der Nervennetze von McCulloch und Pitts aus dem Jahr 1943 charakterisierte Kleene um 1951 die Ereignisse, die endliche Automaten darstellen können, und Rabin und Scott formalisierten 1959 nichtdeterministische Automaten und ihre Entscheidungsprobleme, eine Arbeit, die später mit dem Turing Award gewürdigt wurde.

Key figures

• Stephen Kleene
• Michael Rabin
• Dana Scott
• Anil Nerode

Seminal works

• rabinScott1959
• sipser2013

Frequently asked questions

Wie zeigt man, dass eine Sprache nicht regulär ist?

Das gebräuchlichste Werkzeug ist das Pumping-Lemma, das besagt, dass jede ausreichend lange Zeichenkette in einer regulären Sprache einen Teilstring enthält, der beliebig oft wiederholt werden kann, während er in der Sprache bleibt. Das Finden einer Zeichenkette, die auf diese Weise nicht „gepumpt“ werden kann, beweist, dass die Sprache nicht regulär ist; der Satz von Myhill-Nerode bietet ein alternatives Argument, indem er unendlich viele unterscheidbare Präfixe aufzeigt.

Wenn nichtdeterministische Automaten nicht mächtiger sind, warum werden sie dann verwendet?

Sie sind oft wesentlich kleiner und einfacher zu entwerfen oder aus einem regulären Ausdruck abzuleiten. Die Potenzmengenkonstruktion kann sie bei Bedarf in eine deterministische Form umwandeln, was jedoch mit einem möglichen exponentiellen Kostenanstieg bei der Anzahl der Zustände verbunden sein kann. Nichtdeterminismus ist daher eher ein praktisches Spezifikationswerkzeug als eine Steigerung der Erkennungsleistung.