NFA und DFA sind aequivalent, was bedeutet, dass sie genau gleich viel können. NFA sind zwar (theoretisch) exponentiell schneller als DFA, jedoch kann jeder NFA durch einen DFA simuliert werden.
Solche Automaten sind im Folgenden gedacht für das Erkennen von Sprachen, was bedeutet, dass besonders die Ekzeptierer (eingefärbte States) von NFA und DFA so gesetzt sein müssen, dass am Ende eines Strings dasselbe Resultat herauskommt. Die Beschriftung der States spielt somit grundsätzlich keine Rolle, da nur wichtig ist, in welchem State der Automat stoppt.
Da DFAs eine Untermenge von NFAs sind, ist bereits klar, dass jeder DFA auch ein NFA ist. Um das Umgekehrte zu zeigen genügt der Beweis, dass jeder NFA umgewandelt werden kann. Und dies geht folgendermassen vonstatten:
NFA -> e-frei-NFA
Als ersten Schritt werden die spontanen Übergänge in einem NFA entfernt. Diese e-Übergänge bewirken stets, dass von einem State mit einem e-Übergang zu einem anderen State ohne Verzögerung oder Eingangssignal gewechselt werden kann. Um diese Übergänge zu entfernen bedarf es zwei einfacher Schritte:
Jeder nicht-akzeptierte State, der mittels mindestens einem e-Übergang zu einem Akzeptierer gelangen kann, kann selbst als Akzeptierer eingefärbt werden. Dabei spielt es auch keine Rolle, ob ein Übergang beispielsweise mit "0,e" beschriftet ist, solche Übergänge sind ebenfalls e-Übergänge. Dass diese Abänderung keine Veränderung der akzeptierten Sprache einbringt, liegt auf der Hand, denn wenn ein nicht-Akzeptierer spontan in einen Akzeptierer wechseln kann, so wird auch der String, der in diesem nicht-Akzeptierer stoppen würde in dem Akzeptierer stoppen.
Solange von einem ersten State ein e-Übergang zu einem zweiten führt, so können alle Übergänge, welche beim zweiten State beginnen, auch beim ersten hinzugefügt werden. Der betreffende e-Übergang kann danach gelöscht werden. Wiederum steckt eine einfache Überlegung dahinter: Wenn von einem State spontan in einen zweiten gewechselt werden kann, so bedeutet dies, dass er dieselbe Funktionen annehmen kann, wie der zweite. In Folge müssen also alle States, die von dem zweiten State erreichbar sind auch vom ersten aus erreichbar sein. Sodann ist der e-Übergang überflüssig und kann entfernt werden.
Beispiel: Start ist im Knoten 0
a b c
/---\ /---\ /---\
| V | V | V
#===# #===# #####
| 0 |--------->| 1 |---------># 2 #
#===# e #===# e #####
1. Schritt:
State 1 führt mittels eines e-Übergang zu einem Akzeptierer. Also ist State 1 ebenfalls ein Akzeptierer.
Nun erreicht auch State 0 mittels eines e-Überganges den Akzeptor 1 und ist somit auch ein Akzeptierer.
a b c
/---\ /---\ /---\
| V | V | V
##### ##### #####
# 0 #---------># 1 #---------># 2 #
##### e ##### e #####
2. Schritt:
Der State 1 kann den State 2 mittels eines e-Überganges erreichen. Der State 2 hat einen Übergang (c) zum State 2. Somit bekommt auch der State 1 einen Übergang (c) zum State 2 und der e-Übergang wird gelöscht.
a b c
/---\ /---\ /---\
| V | V | V
##### ##### #####
# 0 #---------># 1 #---------># 2 #
##### e ##### c #####
Der State 0 kann den State 1 mittels eines e-Überganges erreichen. Der State 1 hat einen Übergang (b) zum State 1 und einen Übergang (c) zum State 2. Somit bekommt auch der State 1 einen Übergang (b) zum State 1 und einen Übergang (c) zum State 2 und der e-Übergang wird gelöscht.
a b c
/---\ /---\ /---\
| V | V | V
##### ##### #####
# 0 #---------># 1 #---------># 2 #
##### b ##### c #####
| ^
\-----------------------------/
c
Das Beispiel könnte auch umgekehrt durchgeführt werden (Zuerst die Übergänge vom State 0 und dann die vom State 1 updaten), dies ergibt jedoch genau dasselbe Resultat. Dieses Beispiel ist dem Beispiel aus dem Vorlesungs-Skript nachempfunden. Dort werden jedoch die Übergänge, die von einem State auf den State selbst zurückführen noch in die neu hinzugefügten Übergänge miteinbezogen. Dies ist jedoch nicht nötig und verkompliziert die Sache nur. Wieso dies nicht nötig ist, liegt der Tatsache zugrunde, dass durch das Hinzufügen jeglicher Pfade des States am Ende eines e-Überganges diese bereits implizit hinzugefügt wurden. Also nochmals: Ein e-Übergang bedeutet, dass sämtliche Aufgaben des Ende-States eines solchen Überganges vom betroffenen Anfang-State übernommen werden können. Durch die vorgestellten beiden Schritte ist dies gewährleistet.
Was jedoch beachtet werden muss, ist, dass hier nur zufälligerweise ein DFA vorliegt, es gibt genügend andere Beispiele, bei denen das Entfernen der e-Übergänge noch lange keinen DFA ergibt.
Das zweite Beispiel ist ein solches:
######
b /-----# s1 #<-----\ a
| ###### |
V e | |
/-->#====# \-->#====#
a | | s2 |---------->| s3 |
\---#====# a,b #====#
Als einziger e-Übergang liegt hier der Übergang von s1 zu s3 vor. s1 ist zwar ein Akzeptierer, das heisst jedoch nicht, dass durch den e-Übergang s3 zu einem Akzeptierer wird. Das einzige, was abgeändert werden muss, ist, dass s1 nun noch einen Übergang (a) zu sich selbst erhalten muss. Danach kann der e-Übergang bereits gelöscht werden.
a
/----\
| V
######
b /-----# s1 #<-----\ a
| ###### |
V |
/-->#====# #====#
a | | s2 |---------->| s3 |
\---#====# a,b #====#
e-frei-NFA -> DFA
Um einen e-freien NFA in einen DFA umzuwandeln bedarf es eines etwas komplizierteren Algorithmus. Gegebenfalls können dadurch exponentiell mehr States entstehen, das ist jedoch unumgänglich. Man behilft sich dabei der Überlegung, dass States selber keine Wirkung haben, sondern nur der Weg und der Endpunkt zählt. Die Grundidee ist daher, dass man für jeden State überprüft, zu welchen States man mittels eines bestimmten Eingangssignals gelangen kann. Sodann werden diese States zu einem neuen State zusammengefasst und ein einzelner Übergang dorthin erstellt. Es ist etwas kompliziert, diesen Algorithmus zu erklären, deshalb einfach mal der genaue Ablauf:
1. Schritt:
Gegeben sind die n States, die vom e-freien NFA vorliegen. Nun erstellt man einen vollkommen neuen Automaten, indem man diese n States übernimmt und sie als noch-nicht-bearbeitet markiert. Diese neuen n States haben noch keinerlei Übergänge.
2. Schritt:
Man nimmt sich einen noch-nicht-bearbeiteten State vor und sucht die darin enthaltenen States im ursprünglichen NFA. Nun listet man für alle möglichen Eingangssignale alle States auf, die im ursprünglichen NFA von den durch den noch-nicht-bearbeiteten State beschriebenen States aus erreicht werden können. Für jedes Eingangssignal wird sodann eine einzelne Verbindung zu dem State im DFA erstellt, welcher die Menge der aufgelisteten State beschreibt. Existiert noch kein solcher State, so wird ein neuer erstellt und als noch-nicht-bearbeitet markiert. Beinhaltet ein solcher neu erstellter State mindestens einen als Akzeptierer markierten State im ursprünglichen NFA, so ist dieser neue State selbst ein Akzeptierer.
Der mittlerweile bearbeitete State wird nun als solcher markiert. Dieser zweite Schritt wird solange ausgeführt, bis dass keine weiteren nicht-bearbeiteten States mehr übrig sind.
3. Schritt:
Was nun vorliegt ist bereits ein DFA, jedoch könnte es sein, dass bestimmte States gar nie erreicht werden können. Diese müssen nun noch gelöscht werden: Führt kein Übergang zu einem State oder nur einer, der vom gleichen State aus kommt, so kann der State gelöscht werden (ausser es ist der Start-State).
Als Beispiel wird hier dasselbe Beispiel wie oben genommen:
a
/----\
| V
######
b /-----# s1 #<-----\ a
| ###### |
V |
/-->#====# #====#
a | | s2 |---------->| s3 |
\---#====# a,b #====#
1. Schritt: Es werden 3 neue States erstellt: {s1}, {s2} und {s3}, wovon {s1} ein Akzeptierer ist.
a |
/----\ |
| V |
###### | ###### #====#
b /-----# s1 #<-----\ a | # s1 # | s2 |
| ###### | | ###### #====#
V | |
/-->#====# #====# |
a | | s2 |---------->| s3 | | #====#
\---#====# a,b #====# | | s3 |
#====#
2. Schritt: Vom State s1 aus kann mann mittels a {s1} und mittels b {s2} erreichen.
a
a | /----\
/----\ | | V
| V | ###### b #====#
###### | # s1 #-------->| s2 |
b /-----# s1 #<-----\ a | ###### #====#
| ###### | |
V | |
/-->#====# #====# |
a | | s2 |---------->| s3 | | #====#
\---#====# a,b #====# | | s3 |
#====#
Vom State s2 aus kann man mittels a {s2,s3} und mittels b {s3} erreichen. Ein neuer State {s2,s3} wird erstellt (kein Akzeptor).
a
a | /----\
/----\ | | V
| V | ###### b #====#
###### | # s1 #-------->| s2 |
b /-----# s1 #<-----\ a | ###### /--#====#
| ###### | | b / |
V | | / | a
/-->#====# #====# | / V
a | | s2 |---------->| s3 | | #====#<-/ #=======#
\---#====# a,b #====# | | s3 | | s2,s3 |
#====# #=======#
Vom State s3 aus kann man mittels a {s1} erreichen.
a
a | /----\
/----\ | | V
| V | ###### b #====#
###### | # s1 #-------->| s2 |
b /-----# s1 #<-----\ a | ###### /--#====#
| ###### | | ^ b / |
V | | |a / | a
/-->#====# #====# | | / V
a | | s2 |---------->| s3 | | #====#<-/ #=======#
\---#====# a,b #====# | | s3 | | s2,s3 |
#====# #=======#
Von den States s2 und s3 aus kann man mittels a {s1,s2,s3} und mittels b {s3} erreichen. Es wird ein neuer State erstellt (Akzeptierer).
a
a | /----\
/----\ | | V
| V | ###### b #====#
###### | # s1 #-------->| s2 |
b /-----# s1 #<-----\ a | ###### /--#====#
| ###### | | ^ b / |
V | | |a / | a
/-->#====# #====# | | / V
a | | s2 |---------->| s3 | | #====#<-/ #=======# a ############
\---#====# a,b #====# | | s3 | b | s2,s3 |-------># s1,s2,s3 #
#====#<-------#=======# ############
Von den States s1, s2 und s3 aus kann mittels a {s1,s2,s3} und mittels b {s2,s3} erreicht werden.
a
a | /----\
/----\ | | V
| V | ###### b #====#
###### | # s1 #-------->| s2 |
b /-----# s1 #<-----\ a | ###### /--#====#
| ###### | | ^ b / | a
V | | |a / | a /------\
/-->#====# #====# | | / V a | V
a | | s2 |---------->| s3 | | #====#<-/ #=======#------->############
\---#====# a,b #====# | | s3 | b | s2,s3 | # s1,s2,s3 #
#====#<-------#=======#<-------############
b
3. Schritt: Da hier keinerlei unerreichbare States vorhanden sind, ist die Prozedur abgeschlossen.
DFA -> minimal-DFA
Durch die Eliminierung der unerreichbaren States ist jedoch der Automat noch nicht zwingendermassen minimal. Minimal bedeutet, dass alle States eleminiert sind, die nicht unterscheindbar sind. Unterscheidbar ist ein State von einem anderen genau dann, wenn es eine Folge von Eingangssignalen gibt, die den einen State in einen Akzeptor überführen, den anderen jedoch nicht. Um die nicht-unterscheidbaren States zu erkennen, behilft man sich einer Tabelle. Hier ein neues Beispiel (Start im State 0):
a
/---\
| V
#===# a #####--------\ | #0# ? ? ? ? ?
/-->| 3 |-------># 4 # |b |
a| #===# #####<---\ | | |1| ? ? ? ?
| | ^ a| V |
##### | | #===#<--\ | |2| ? ? ?
# 0 # |b a| | 1 | |b |
##### | | #===#---/ | |3| ? ?
| V b | |
b| #===#------->#===# | #4# ?
\-->| 5 | | 2 | |
#===#<-------#===# | |5|
| ^ b
\---/
a
Jedes Fragezeichen steht für den Krezuzungspunkt zwischen zwei States, die auf der Diagonalen angeordnet sind. An diesen Fragezeichen gibt man nun nach und nach den String ein, welche die betreffenden beiden States unterscheidbar macht. Zuerst trägt man nun diejenigen States ein, die ohne ein Übergang bereits unterscheidbar sind. Genaugenommen sind dies alle Kombinationen von Akzeptoren und nicht-Akzeptoren. Eingetragen wird ein epsilon, um anzuzeigen, dass bereits der leere String reicht, um die States zu unterscheiden:
a
/---\
| V
#===# a #####--------\ | #0# e e e ? e
/-->| 3 |-------># 4 # |b |
a| #===# #####<---\ | | |1| ? ? e ?
| | ^ a| V |
##### | | #===#<--\ | |2| ? e ?
# 0 # |b a| | 1 | |b |
##### | | #===#---/ | |3| e ?
| V b | |
b| #===#------->#===# | #4# e
\-->| 5 | | 2 | |
#===#<-------#===# | |5|
| ^ b
\---/
a
Als nächstes schaut man sich jedes verbleibende Päärchen an, ob der Input a oder b dazu führt, dass sie in einen unterscheidbaren State gelangen. Gelingt dies, so trägt man diesen ein. Um die Sache etwas zu vereinfachen schaut man im Automaten nach, zu welchen States man mit einem Eingangssignal kommt und betrachtet danach in der Tabelle die Stelle, die durch diese beiden States gegeben wird. Steht dort ein e, so sind sie unterscheidbar und man kann an der ursprünglich betrachteten Stelle das Eingangssignal eintragen. Landen beide ursprünglichen States im selben State, so sind sie nicht durch dieses Eingangssignal nicht unterscheidbar. Betrachtet man beispielsweise die beiden States 0 und 4 und gibt das Signal a hinein, so wird von 0 aus der State 3 und von 4 aus der State 4 erreicht. Nun kuckt man nach, ob 3 und 4 unterscheidbar sind. Da ein e eingetragen ist, kann man nun an der Stelle 0,4 ein a eintragen. So füllt man nun einmal alle möglichen Fragezeichen aus:
a
/---\
| V
#===# a #####--------\ | #0# e e e a e
/-->| 3 |-------># 4 # |b |
a| #===# #####<---\ | | |1| ? ? e a
| | ^ a| V |
##### | | #===#<--\ | |2| ? e a
# 0 # |b a| | 1 | |b |
##### | | #===#---/ | |3| e a
| V b | |
b| #===#------->#===# | #4# e
\-->| 5 | | 2 | |
#===#<-------#===# | |5|
| ^ b
\---/
a
Da noch nicht alle Fragezeichen entfernt sind, geht es weiter mit den States, die erst durch zwei Eingangssignale unterschieden werden können. Wiederum probiert man die Eingangssignale a und b bei den restlichen Fragezeichen aus und überprüft, ob die Ziel-States unterscheidbar sind. Grundsätzlich gilt: Sobald durch eine Eingabe zwei States erreicht werden, die bereits einen Eintrag in der Tabelle haben, so kann der dortige Eintrag übernommen und das hineingegebene Signal vorne angehängt werden. Mittels dieser Methode füllt man die Tabelle ständig weiter auf, bis dass keine Fragezeichen mehr vorhanden sind, oder diese zu keinem bekannten Ziel führen:
a
/---\
| V
#===# a #####--------\ | #0# e e e a e
/-->| 3 |-------># 4 # |b |
a| #===# #####<---\ | | |1| ba ba e a
| | ^ a| V |
##### | | #===#<--\ | |2| ? e a
# 0 # |b a| | 1 | |b |
##### | | #===#---/ | |3| e a
| V b | |
b| #===#------->#===# | #4# e
\-->| 5 | | 2 | |
#===#<-------#===# | |5|
| ^ b
\---/
a
Was die beiden ba-Einträge bedeuten ist, dass beispielsweise die States 1 und 2 dadurch unterschieden werden können, indem man ihnen zuerst ein b und dann beim jeweiligen Zielknoten ein a einspeist. Übrig geblieben sind nun nur noch die beiden States 2 und 3, welche durch kein Eingangssignal unterschieden werden können. Als einzige Möglichkeit bleibt nur noch, dass sie nicht unterscheidbar und somit gleichwertig sind. In der Tabelle kann man das als Ø vermerken, das Interessante daran ist jedoch folgendes:
Da die beiden States nicht unterscheidbar sind, kann man sie ohne Verlust zusammenlegen. Aus den beiden Knoten 2 und 3 wird ein neuer Knoten x, der jedoch sämtliche Übergänge der ursprünglichen Knoten aufweist:
a
/---\
| V
#####--------\ | #0# e e e a e
a/--># 4 # |b |
| #####<---\ | | |1| ba ba e a
| a| V |
##### a #===# #===#<--\ | |2| Ø e a
# 0 #------->| x | | 1 | |b |
##### #===# #===#---/ | |3| e a
| b| ^ |
b| #===#<-/ | | #4# e
\-->| 5 | |b |
#===#-----/ | |5|
| ^
\---/
a
Nun hat man einen minimal-DFA.