Kleines Nachschlagewerk Informatik
Endliche Automaten
Worum geht es?
Hier soll der Sonderfall des endlichen Automaten beschrieben werden. Endliche Automaten sind die einfachsten Automaten.
Definition
Ein endlicher Automat besitzt eine endliche Zahl von Zuständen. Sind die Übergänge eindeutig, spricht man von einem deterministischen endlichen Automaten (DEA), andernfalls von einem nichtdeterministischen endlichen Automaten (NEA). NEAs sind keineswegs exotisch. Wandelt man reguläre Grammatiken in Automaten um, ergeben sich oft NEAs.

Zur formalen Definition gehören wieder die Zustände (inklusive der Angabe von Start- und Endzuständen), das Eingabealphabet und die Überführungsfunktion. Im Falle von Ausgaben muss noch das Ausgabealphabet angegeben werden.
Beispiel 1 - Kugelschreiber
Ein Kugelschreiber besitzt die Zustände "an" und "aus". Das Eingabezeichen d kann schalten.





alter ZustandZeichenneuer Zustand
andaus
ausdan
Beispiel 2 - NEA
Im Bild unten ist ein NEA gegeben. Wird in s0 eine 1 gelesen, kann der Automat in s0 bleiben oder zu s1 übergehen. Das ist ein Automat, der beliebig lange Binärzahlen, deren vorletzte Ziffer eine 1 ist, akzeptieren kann.



Umwandlung NEA in DEA
NEAs sind nicht eindeutig und damit schwer zu programmieren. Ihre Umwandlung in DEAs lässt sich nach einem Algorithmus erledigen. Die Grundidee lässt sich in zwei Punkten zusammenfassen: Ein Beispiel soll dies demonstrieren. Ausgang ist der NEA aus obigen Beispiel. Die Überführungsfunktion ist d.
1. Schrittd(s0,0)=s0gibt es schon
d(s0,1) = s0 v s1 = s0s1neuer Zustand
2. Schrittd(s0s1, 1) = d(s0,1) v d(s1,1) = s0s1 v s2 = s0s1s2neuer Zustand
d(s0s1, 0) = d(s0,0) v d(s1,0) = s0 v s2 = s0s2neuer Zustand
3. Schrittd(s0s1s2, 0) = d(s0,0) v d(s1,0) v d(s2,0) = s0 v s2 = s0s2gibt es schon
d(s0s1s2, 1) = d(s0,1) v d(s1,1) v d(s2,1) = s0s1 v s2 = s0s1s2gibt es schon
d(s0s2, 0) = ds(0,0) v d(s2,0) = s0gibt es schon
d(s0s2,1) = d(s0,1) v d(s2,1) = s0s1gibt es schon
Wie man sieht, werden die Übergänge der neuen Zustände des DEA in die Übergänge des alten NEA zerlegt. Aus diesen Übergängen ergeben sich evtl. neue Zustände.

Übergänge von s2 existieren nicht, somit tauchen sie in der Umwandlung auch nicht auf. Entstanden sind die neuen Zustände s0s1, s0s1s2, s0s2. Weggefallen sind s1 und s2. Im dritten Schritt kommen keine neuen Zustände hinzu, die Umwandlung ist abgeschlossen.

Man sieht auch, dass die Zahl der Zustände stark zunehmen kann (maximal 2 hoch n).