Theoretische Informatik - Endliche Automaten

Nächste Seite: Endliche Automaten und reguläre Aufwärts: Reguläre Sprachen Vorherige Seite: Reguläre Sprachen Inhalt

Unterabschnitte

Endliche Automaten

Definition: Deterministischer endlicher Automat (DFA)

Ein DFA ist ein 5er-Tupel $M=(Q,\Sigma,\delta,q_{0},F)$ bestehend aus

Q:	Endlicher Zustandsmenge
$\Sigma$ :	endliches Alphabet, welches für das Eingabewort
	und bei den Übergängen benutzt wird
$\delta$ :	Übergangsfunktion $\delta:Q\times\Sigma\rightarrow Q$
$q_{0}$ :	Startzustand aus
F:	Endzustandsmenge $F\subseteq Q$

Gibt es keine passende Übergangsfunktion mehr und das Eingabewort ist noch nicht ganz gelesen, so verwirft der Automat.
Ist der Automat, wenn das Eingabewort komplett gelesen ist in einem Endzustand, so akzeptiert er⁵⁰.
Ist er nicht in einem Endzustand bei Ende des Wortes, so verwirft er.

Automaten gehen auf dem Band mit jedem Zustandwechsel immer eine Zelle nach rechts.

Manchmal benötigt man einen DFA, der solange läuft, bis das Eingabewort abgearbeitet ist. Mann kann hierfür einen Fangzustand generieren, in den alle nicht definierten Übergangsfunktionen gehen, wenn also an dieser Stelle eigentlich der Automat schon verwerfen müßte. Dieser Fangzustand ist nicht in der Endzustandsmenge, weshalb dann verworfen wird, wenn das Wort zuende ist.

Lauf

Man kann die Zustände, durch die ein DFA beim akzeptieren oder verwerfen eines Wortes läuft hintereinander auflisten. Eine solche Liste nennt man Lauf. Man kann einen akzeptierenden oder verwerfenden Lauf haben. Haben wir einen verwerfenden Lauf so schreiben wir an das Ende des Laufes ein $\bot$ , also z.B

$\begin{displaymath}q_{0}q_{1}\ldots q_{i}\bot\end{displaymath}$

Definition: Nichtdeterministischer endlicher Automat (NFA)

Ein NFA ist ein Automat, der in mehr als einen Zustand mit dem gleichen Zeichen im Eingabewort wechseln kann. Grafisch gesprochen gibt es also mehrere Pfeile vom selben Zustand mit der selben Inschrift zu unterschiedlichen Folgezuständen.
Des weiteren kann ein NFA mehr als einen Startzustand haben.
Aus den zur Auswahl stehenden Zustandswechseln und Startzuständen wird nichtdeterministisch einer gewählt, so daß - wenn möglich - der NFA einen akzeptierenden Lauf hat.

$\delta:Q\times\Sigma\rightarrow 2^{Q}$	Übergangsfunktion
$Q_{0}\subseteq Q$	Menge der Startzustände

$2^{Q}$ bezeichnet hierbei die Potenzmenge. Eine Potenzmenge ist die Menge aller Teilmengen einer Menge, also hier alle Teilmengen von Q.

Fußnoten

... er ⁵⁰: Dies ist anders als bei Turingmaschinen. Turingmaschinen akzeptieren sofort, wenn sie in einen Endzustand kommen. Automaten akzeptieren nur, wenn das Wort zuende ist und sie in einem Endzustand sind. Sie laufen über den Endzustand hinweg, wenn das Wort noch nicht zuende ist.

Nächste Seite: Endliche Automaten und reguläre Aufwärts: Reguläre Sprachen Vorherige Seite: Reguläre Sprachen Inhalt