Eine "regular Expression" ist ein String, welcher bei serieller Eingabe in einen bestimmten Automaten (egal ob NFA oder DFA) in einem Akzeptor landet.
Die Menge aller möglichen Strings, die durch einen bestimmten Automaten akzeptiert werdn, nennt man eine Sprache. Mathematisch geschrieben: L ist Teilmenge von A*.
Eine regular Expression kann auch als Wort einer Sprache definiert werden. w ist Element von A*.
Was nun noch hinzukommt sind die Definitionen Union (L1 U L2), Katenation (L1 * L2) und der Kleene-Stern (L*):
Union
Eine Union ist nichts anderes als die Zusammenlegung zweier Sprachen, was wiederum eine (neue) Sprache ergibt. Sowohl alle Wörter der einen, als auch alle der anderen müssen in dieser neuen Sprache enthalten sein. Der dahinterstehende Automat kann sehr leicht konstruiert werden. Man definiert einfach einen neuen Startzustand und erstellt je einen e-Übergang zum bisherigen Start der beiden Sprachen. Beispiel:
Die beiden einzelnen Sprachen A und B (Start ist jeweils bei den States 0 und 3):
A: #===# | B: #####<--\
/-----| 0 | | # 3 # |a
a| #===# | /--#####---/
| | b| ^
V a | V b\--------\
#===#<-----------#####<--\ | /---#===# #####
| 1 | # 2 # |b | a| | 4 |--------># 5 #
#===#----------->#####---/ | \-->#===# b #####
a,b |
Die zusammengelegte Sprache:
#===# #=======# #####<--\
/-----| 0 |<--------| START |-----------># 3 # |a
a| #===# e #=======# e /--#####---/
| b| ^
V a V b\--------\
#===#<-----------#####<--\ /---#===# #####
| 1 | # 2 # |b a| | 4 |--------># 5 #
#===#----------->#####---/ \-->#===# b #####
a,b
Katenation
Die Katenation ist nichts anderes als die Hintereinanderlegung zweier Sprachen, was wiederum eine (neue) Sprache ergibt. Die neue Sprache erkennt also alle Wörter, die Zusammengesetzt sind aus zuerst einem Wort der ersten und dann einem der zweiten Sprache. Um den Automaten an eine solche Sprache anzupassen müssen einfach alle Wortende der ersteren Sprache mit dem Anfang der zweiten durch einen e-Übergang verbunden werden. Die Wortenden einer Sprache können aber nur die Akzeptoren sein, da das Wort sonst nicht in der Sprache gewesen sein kann. Fazit: Man verbindet sämtliche Akzeptoren der ersteren Sprache mit dem Start-State der zweiteren Sprache mit einem e-Übergang. Hier das gleiche Beispiel wie oben:
Die beiden einzelnen Sprachen A und B (Start ist jeweils bei den States 0 und 3):
A: #===# | B: #####<--\
/-----| 0 | | # 3 # |a
a| #===# | /--#####---/
| | b| ^
V a | V b\--------\
#===#<-----------#####<--\ | /---#===# #####
| 1 | # 2 # |b | a| | 4 |--------># 5 #
#===#----------->#####---/ | \-->#===# b #####
a,b |
Die hitereinandergelegte Sprache:
#===# e #####<--\
/-----| 0 | /----------------------># 3 # |a
a| #===# | /--#####---/
| | b| ^
V a | V b\--------\
#===#<-----------#####<--\ /---#===# #####
| 1 | # 2 # |b a| | 4 |--------># 5 #
#===#----------->#####---/ \-->#===# b #####
a,b
Kleene-Star
Der Kleene-Star L* bedeutet nichts anderes als beliebig viele (auch 0) Wörter einer Sprache hintereinander. Liegt also beispielsweise das Wort "abaa" in L, so liegt "abaaabaaabaaabaa" in L*. Um eine solche Sprache zu konstruieren müssen einfach alle möglichen Wortenden wiederum mit dem Start-State über einen e-Übergang verbunden werden. Zusätzlich muss noch ein neuer Akzeptor als Start-State eingeführt werden, der ebenfalls mit einem e-Übergang auf den bisherigen Start zeigt. Dieser neue Start ist dafür da, dass auch das leere Wort (definitionsgemäss) in L* enthalten ist. War der bisherige Start-State bereits ein Akzeptierer, so spielt dies jedoch keine Rolle. Beispiel (Start bei 0):
L:
b
#===# b #####<----------#===#
| 0 |----------># 1 # | 2 |
#===# /-->#####---------->#===#
| / | ^ a
|a a/ b| \
V / V \a
#===# / #===# \--------#####
| 3 |--/ | 4 |----------># 5 #
#===# #===# b #####
L*:
#########
# START #
#########
| e
e| /--------------\
V V | b
#===# b #####<----------#===#
/--->| 0 |----------># 1 # | 2 |
| #===# /-->#####---------->#===#
| | / | ^ a
|e |a a/ b| \
| V / V \a
| #===# / #===# \--------#####
| | 3 |--/ | 4 |----------># 5 #
| #===# #===# b #####
\-------------------------------------/
Umwandlung einer regular Expression in einen DFA
Die Umwandlung einer regular Expression erfolgt hier zuerst in einen DFA mit e-Übergängen (also eigentlich ein NFA), welcher danach mit den bekannten Regeln leicht in einen DFA umgewandelt werden kann. Als Beispiel dient hier die regular Expression
ab*(b|aa)(ab)*
Als erstes definiert man einen Start-State und einen Endstate, welcher bis auf weiteres der einzige Akzeptor sein wird. Man merkt sich nun den Start-State als den aktuellen State.
#=======# ######## | START | # ENDE # #=======# ########
Sodann wird die Expression von links nach rechts traversiert, indem folgende Regeln abgearbeitet werden (Sämtliche folgende States sind nicht-Akzeptoren!):
Tritt in der Expression ein einfacher Buchstabe auf (hier z.B. a), so wird ein neuer State erstellt und vom aktuellen State aus ein Übergang mit dem Buchstaben zu diesem neuen State erstellt.
#=======# a #===# ######## | START |---->| | # ENDE # #=======# #===# ########
Tritt ein einzelner Buchstabe mit Stern auf (z.B. b*), so wird beim aktuellen State ein Übergang zu sich selbst mit diesem Buchstaben erstellt.
b
/---\
| V
#=======# a #===# ########
| START |---->| | # ENDE #
#=======# #===# ########
Würde nach einem solchen Stern-Buchstaben gleich noch einer folgen, so erstellt man einen neuen State und macht einen e-Übergang vom aktuellen zu diesem neuen State. Sodann kann der neue State als der Aktuelle angesehen werden.
Tritt eine öffnende Klammer auf (, so erstellt man einen neuen State, macht vom Aktuellen aus einen e-Übergang zu diesem, betrachtet den neuen State als den Aktuellen, markiert den aktuellen State zusätzlich als ein neuer Startknoten und erstellt glechzeitig einen Endknoten. Die vorherigen Start- und End-States werden nun sozusagen auf einem Stapel abgelegt, das heisst deaktiviert.
b
/---\
| V
#=======# a #===# e #===# #===#
| START |---->| |---->| ( | | ) |
#=======# #===# #===# #===#
########
# ENDE #
########
Nun tritt wiederum ein einzelner Buchstabe auf:
b b #===#
/---\ /--------->| |
| V | #===#
#=======# a #===# e #===# #===#
| START |---->| |---->| ( | | ) |
#=======# #===# #===# #===#
########
# ENDE #
########
Tritt ein ODER-Zeichen auf |, so wird vom aktuellen State aus zum aktuellen End-State eine e-Verbingung gelegt. Sodann wird der momentane Start-State wieder zum aktuellen State.
b b #===# e
/---\ /--------->| |----------\
| V | #===# V
#=======# a #===# e #===# #===#
| START |---->| |---->| ( | | ) |
#=======# #===# #===# #===#
########
# ENDE #
########
Nun treten wieder zwei einzelne Buchstaben auf:
b b #===# e
/---\ /--------->| |----------\
| V | #===# V
#=======# a #===# e #===# #===#
| START |---->| |---->| ( | | ) |
#=======# #===# #===# #===#
| #===# a #===#
\---->| |---->| |
a #===# #===#
########
# ENDE #
########
Tritt eine schliessende Klammer auf ), so wird vom aktuellen State aus eine e-Verbindung zum aktuellen End-State gezogen. Dieser End-State ist nun der Aktuelle. Sodann werdend die alten Start- und End-States vom Stapel geholt und wieder aktiviert.
b b #===# e
/---\ /--------->| |----------\
| V | #===# V
#=======# a #===# e #===# #===#
| START |---->| |---->| ( | | ) |
#=======# #===# #===# #===#
| #===# a #===# ^
\---->| |---->| |-----/
a #===# #===# e
########
# ENDE #
########
Wiederum tritt eine Klammerung und danach zwei einzelne Buchstaben mit abschliessender Klammer auf.
b b #===# e
/---\ /--------->| |----------\
| V | #===# V
#=======# a #===# e #===# #===#
| START |---->| |---->| ( | | ) |--\
#=======# #===# #===# #===# |
| #===# a #===# ^ |
\---->| |---->| |-----/ |
a #===# #===# e |
e |
/------------------------------------------------------/
|
| #===# a #===# b #===# e #===# ########
\->| ( |---->| |---->| |---->| ) | # ENDE #
#===# #===# #===# #===# ########
Tritt nun nach einer schliessenden Klammer ein Stern * auf, so ruft man sich nochmals den Startstate der Klammerung in Erinnerung und zieht vom aktuellen (welcher das Ende der Klammerung ist) zu diesem einen e-Übergang. Sodann wird dieser Start-State zum Aktuellen.
b b #===# e
/---\ /--------->| |----------\
| V | #===# V
#=======# a #===# e #===# #===#
| START |---->| |---->| ( | | ) |--\
#=======# #===# #===# #===# |
| #===# a #===# ^ |
\---->| |---->| |-----/ |
a #===# #===# e |
e |
/------------------------------------------------------/
|
| #===# a #===# b #===# e #===# ########
\->| ( |---->| |---->| |---->| ) | # ENDE #
#===# #===# #===# #===# ########
^ |
\-----------------------------/
e
Ist man am Ende der regular Expression angelangt, so muss nur noch vom Aktuellen State ein e-Übergang zum Ende gezogen werden.
b b #===# e
/---\ /--------->| |----------\
| V | #===# V
#=======# a #===# e #===# #===#
| START |---->| |---->| ( | | ) |--\
#=======# #===# #===# #===# |
| #===# a #===# ^ |
\---->| |---->| |-----/ |
a #===# #===# e |
e |
/------------------------------------------------------/
|
| e
| /------------------------------------------\
| | V
| #===# a #===# b #===# e #===# ########
\->| ( |---->| |---->| |---->| ) | # ENDE #
#===# #===# #===# #===# ########
^ |
\-----------------------------/
e
Was nun hier vorliegt ist ein Automat, der die Sprache, welche durch die regular Expression gegeben ist, erkennen kann. Wenn man nun aus diesem NFA ein DFA machen möchte, so kann man sich der bereits vorgestellten Methoden behelfen. Sobald die e-Übergänge entfernt sind, liegt ein DFA vor. Dieser ist aber noch nicht zwingend minimal!
Umwandlung DFA in regular Expression
Um einen DFA in eine regular Expression umzuwandeln überlegt man sich theoretisch für jeden State, wie man zu einem anderen (Zielknoten) kommen kann. Es gibt dabei grundsätzlich zwei Möglichkeiten: Direkt oder indirekt über einen weiteren Knoten. Mit welchem String man direkt zu einem Zielknoten kommt ist nicht schwierig, es ist einfach der String, der durch den direkten Übergang gegeben ist. Der Pfad über einen dritten ist jedoch auch keine Zauberei. Es ist der String, der zusammengesetzt ist aus dem Übergang vom ersten State zum dritten plus dem eventuellen Übergang vom dritten zu sich selbst plus der Übergang vom dritten zum Zielknoten.
Am besten kann dies anhand eines Beispiels erklärt werden. Gegeben sei der folgende DFA mit Start im Knoten 0:
b
#===#---------------->#===#<--\
| 0 | | 2 | |b
#===#<----------------#===#---/
^ \ a ^
| a\---->#####--------/b
\a # 1 #
\---------#####
Um ein Ziel vor Augen zu haben erweitern man diesen DFA noch um zwei Knoten: Ein neuer Start-State mit einem e-Übergang zum bisherigen Start-State 0, und ein End-State, zu dem sämtliche Akzeptoren noch zusätzlich einen e-Übergang hinzubekommen. Dieser End-State ist nun der einzige Akzeptor im Automaten.
b
#=======# e #===#---------------->#===#<--\
| START |--->| 0 | | 2 | |b
#=======# #===#<----------------#===#---/
^ \ a ^
| a\---->#===#--------/b ########
\a | 1 | e # ENDE #
\---------#===#--------------->########
Nun schaut man sich beispielsweise den State 2 an. Wenn dieser State gelöscht werden würde, was für neue Übergänge müssten dann erstellt werden, damit der Automat noch gleich arbeitet? Betrachtet man nun zuerst einmal den State 0. Von hier aus könnte man theoretisch über b wieder zu sich selbst zurückkommen. Dabei benötigt man jedoch ein "b", um zum Knoten 2 zu kommen, hat dann die Möglichkeit, beliebig viele bs zu schreiben, um im State 2 zu bleiben (b)* und benötigt danach noch ein "a", um wieder zum State 0 zurückzukommen. Dies ergibt also den String "bb*a", welcher nun dem State 0 problemlos hinzugefügt werden kann:
bb*a
/---\
| V b
#=======# e #===#---------------->#===#<--\
| START |--->| 0 | | 2 | |b
#=======# #===#<----------------#===#---/
^ \ a ^
| a\---->#===#--------/b ########
\a | 1 | e # ENDE #
\---------#===#--------------->########
Betrachtet man nun noch den State 1, so sieht man, dass man von ihm aus über den State 2 zum State 0 gelangen kann. Und zwar mit dem String "b" plus "(b)*" plus "a" = "bb*a". Diesen Übergang von 1 zu 0 kann nun ebenfalls eingetragen werden. Zudem hat der State 2 nun keine wichtige Funktion mehr und kann bedenkenlos gelöscht werden, da alle Nachbarknoten nun keinen Umweg mehr über 2 machen müssen, da sie ja nun direkte Wege besitzen.
bb*a
/---\
| V
#=======# e #===#
| START |--->| 0 |<-------\bb*a
#=======# #===# |
^ \ |
| a\---->#===# ########
\a | 1 | e # ENDE #
\---------#===#--------------->########
Zusätzlich könnte man nun noch bemerken, dass der State 1 bereits einen Weg zu 0 besitzt, nämlich derjenige, der mit "a" beschriftet ist. Somit ergibt dies zusammen einen Weg, der mit dem String "a|bb*a" von 1 zu 0 führt. Dies ist jedoch dasselbe wie "b*a".
bb*a
/---\
| V
#=======# e #===#
| START |--->| 0 |<-------\b*a
#=======# #===# |
\ |
a\---->#===# ########
| 1 | e # ENDE #
#===#--------------->########
Betrachtet man nun den Knoten 0. Würde dieser gelöscht werden, so müsste der Knoten 1 einen neuen Weg zurück zu sich selbst erhalten. Der dazu gehörige String ist "b*a" plus "(bb*a)*" plus "a" = "b*a(bb*a)*a". Nun gibt es aber auch einen Weg vom State START zum State 1. Der dazugehörige String ist "e" plus "(bb*a)*" plus "a" = "(bb*a)*a". Nun kann der State 0 wiederum gelöscht werden.
#=======#
| START |----\ b*a(bb*a)*a
#=======# | /---\
| | V
(bb*a)*a| #===# ########
\ | 1 | e # ENDE #
\---------#===#--------------->########
Nun bleibt nur doch der Knoten 1 übrig. Würde er entfernt werden, so entstünde ein direkter Weg von START zu ENDE mit den String "(bb*a)*a" plus "(b*a(bb*a)*a)*" plus "e" = "(bb*a)*a(b*a(bb*a)*a)*". Dieser Ausdruck ist derselbe wie "((a|b)b*a)*a". Dies ist auch das Resultat dieser Aufgabe: die gesuchte regular Expression.