Endliche Automaten

Deterministische Endliche Automaten

Ein DEA akzeptiert Zeichen einer Sprache und wechselt je nach Eingabezeichen und derzeitigem Zustand eindeutig in einen anderen Zustand. DEAs bestehen aus einem Startzustand, einem Eingabealphabet, Übergangsfunktionen und Endzuständen.

Deterministisch: Folgezustände sind klar und eindeutig definiert.

Eindeutigkeit: Es gibt keine Wahlmöglichkeiten oder Übergänge ohne Eingabe.

Formale definition: $A = (Q, \Sigma, \delta, z_0, F)$, wobei:

Zeichen	Beschreibung
$Q$	Endliche Menge an Zuständen.
$\Sigma$	Endliches Eingabealphabet.
$\delta$	Endliche Menge an Übergangsfunktionen.
$z_0$	Ein Startzustand aus $Q$.
$F$	Endliche Teilmenge von Endzuständen aus $Q$.

Akzeptoren

Ein Akzeptor ist ein spezieller DEA, welcher kontrolliert, ob eine Zeichenkette ein Wort einer Sprache ist. Mehr Informationen gibt es im Glossar.

Zustandsdiagramm

Das Zustandsdiagramm ist ein Graph der Zustände und Übergangsfunktionen eines Automaten. Hierbei werden Zustände als Knoten und Übergangsfunktionen als Pfeile mit Bedingungen dargestellt. Die Endzustände werden mit einem Doppelkreis dargestellt. Der Startzustand wird mit einem Pfeil von Außen gekennzeichnet.

Übergangstabelle

Tabellarische Darstellung der Zustände und Übergänge in einem DEA. Auch im Glossar des Akzeptors beschrieben.

Reguläre Ausdrücke

Regular expressions! Die gibt’s auf https://regex101.com. Werde ich hier nicht ansprechen, da ich diese mittlerweile wie eine Sprache flüssig spreche. Also metaphorisch gemeint.

Grenzen von DEAs

Ein DEA hat keine Form von Speicherplatz. Er hat auch keine “Funktionen”, welche man aufrufen kann, nur um dann wieder an den vorherigen Zustand zurückzukehren. Dies macht es fundamental unmöglich, Zeichenketten zu verarbeiten, die z.B. Klammern enthalten. Es kann keinen DEA geben, welcher kontrolliert, dass für jede öffene Klammer ( auch eine schließende Variante ) später in der Kette auftaucht.