Zwischenbetrachtung / Resümee:
Wir kennen bereits den Mechanismus des Erkennens (durch
Automaten) einer Sprache (erzeugt über einem endlichen Alphabet).
Diese Sprachen, losgelöst von den
Akzeptoren, genauer zu betrachten und so den Mechanismus des Erzeugen (durch
Grammatiken oder reguläre Ausdrücke) kennenzulernen ist Aufgabe der folgenden Absätze.
Sprachen wurden von
Noam Chomsky genauer untersucht.
Von ihm stammt die Unterteilung der Klasse aller Sprachen in vier Kategorien:
Sprachen der Stufe: | sind: | und werden akzeptiert von: |
0 | aufzählbare Sprachen | Turingmaschinen |
1 | kontextsensitive Sprachen | linear beschränkten Automaten |
2 | kontextfreie Sprachen | Push-Down-Automaten / Kellerautomaten |
3 | reguläre Sprachen | deterministischen Automaten |
| ausführlicher bitte! |
Unser erstes Ziel ist es, die Sprachklasse zu klassifizieren, die wir durch
endliche Akzeptoren erkennen.
Es wird gezeigt werden, daß dies genau der Klasse der regulären Sprachen entspricht:
4.3. Reguläre Sprachen
Definition N: (Syntaxdefinition)
Sei X ein Alphabet und V={ ( , ) , * , È, ·, Æ } ein Vorrat an Zeichen.
Dann ist die Mengen der regulären Ausdrücke Reg(X) folgendermaßen definiert:
- "xÎX( xÎReg(X) ) Û XÍReg(X)
- ÆÎReg(X)
- "R,QÎReg(X)( (RÈQ)ÎReg(X) Ù (R·Q)ÎReg(X) )
- "RÎReg(X)( R*ÎReg(X) )
- Reg(X) ist kleinste Teilmenge von (XÈV)*, die i) bis iv) erfüllt
Beispiele:
Sei X={x1,x2,x3} Dann sind u.a. folgende Ausdrücke reguläre Ausdrücke:
- x1
- (((x2·x1) ·x3)Èx3)
- ((x1·x2)*Èx1)*
Diese Folgen, bestehend aus Zeichen und Elementen aus XÈV sind bisher jedoch sinnleer!
Sie entstehen durch bloßes Anwenden der Regeln i) bis iv).
Die nun notwendige Interpretation folgt jetzt:
Definition O: (Semantikdefinition)
Die Bedeutung eines regulären Ausdruckes über X wird durch folgende Abbildung s:Reg(X)®2X* festgelegt, die wie folgt induktiv definiert ist:
- xÎX Þ s(x)={x}
- s(Æ)=Æ
- "R,QÎReg(X)( s(RÈQ)=s(R)Èd(Q) Ù s(R·Q)=s(R)·d(Q) )
- "RÎReg(X)( s(R*)=s(R)* )
Reg(x) ist genaugenommen nur eine Menge von Zeichenreihen, den regulären Ausdrücken.
Diesen Ausdrücken gibt s eine Bedeutung, die Interpretation.
Diese Bedeutung ist einen Sprache.
s(x) ist die Sprache, die der reguläre Ausdruck x beschreibt.
Ist s(r) = s(r'), so heißen r und r' äquivalent.
Beispiele:
- s( Æ ) = Æ
dem sinnleeren Zeichen "Æ" wird die leere Menge zugeordnet;
- s( Æ* ) = s(Æ)*=Æ*={e}
der sinnleeren Zeichenfolge "Æ*" wird nach Regel iv) der Semantikdefinition die mengentheoretische *-Bildung von "s(Æ)" zugewiesen, was seinerseits wiederum nach Regel ii) die leere Menge ist. Nach Definition der *-Bildung folgt: Æ*={e};
Bemerkung:
ergänzend zu den Semantikregeln gibt es Prioritätsregeln, die eine Änderung der Syntax mit sich bringen, jedoch die Bedeutung des Ausdruckes unverändert lassen:
- "·" wird vor "È" interpretiert
- Weglassen äußerer Klammern
- Weglassen des Zeichens "·"
Beispiel:
- "(x1È(x2·x3))"
entspricht "x1È(x2·x3)" nach Prioritätsregel ii)
entspricht "x1Èx2·x3" nach Prioritätsregel i) und ii)
entspricht "x1Èx2x3" nach Prioritätsregel iii)
Definition P:
Sei X ein Alphabet.
Eine Sprache LÍX* heißt reguläre Sprache, wenn es einen regulären Ausdruck RÎReg(X) mit s(R)=L gibt.
(LÍX* heißt reguläre Sprache :Û $RÎReg(X)( s(R)=L ).
Die Menge aller regulären Sprachen über X bezeichnen wir mit R(X).
Die Klasse aller regulären Sprachen bezeichnen wir mit R.
Äquivalenzproblem für reguläre Ausdrücke:
Sei R ein regulärer Ausdruck mit: R = a(a*Èb*)* È (bÈc)(aÈbÈc)* È (ca)* , |
dann folgt für s(R): s(R) = { |
wÎX* | |
|
wÎ{a,b}* und w beginnt mit einem a |
|
|
oder |
wÎ{a,b,c}* und w beginnt nicht mit a |
|
|
oder |
w=e |
} |
|
|
|
Der dritte Fall (ca)* kann auf w=e "runtergewertet" werden;
Dies ergibt sich aus: (ca)*\{e} Í (bÈc)(aÈbÈc)*, somit muß nur noch der Fall {e} hinzugefügt werden.
Sei R‘ ein regulärer Ausdruck mit: R‘ = a(aÈb)* È (bÈc)(aÈbÈc)* È Æ*
Ersichtlich ist: s(R) = s(R‘)
Aus dieser Betrachtung ergibt sich folgende
Frage: Gibt es einen Algorithmus, der für jedes beliebige Alphabet X und für je zwei reguläre Ausdrücke R,R’ÎReg(X) entscheidet, ob s(R) = s(R‘)?
Antwort: Ja, dieses Problem ist algorithmisch lösbar, aber sehr aufwendig (NP-hart [nichtdeterministisch in polynomiel viel Zeit lösbar]).
Satz Q: (Gleichheit von R und DA)
Die Klasse aller regulären Sprachen und die Klasse aller, durch endliche
Automaten akzeptierbarer Sprachen ist gleich. (R=DA)
Beweis von Satz Q:
Zeige zuerst die mengentheoretische Inklusion von R in DA ("Í"):
Definition N Þ R ist kleinste Klasse von Sprachen, die
die leere Menge enthält,
die alle Mengen {x} (mit xÎX) enthält,
die gegen Vereinigung, Konkatenation und *-Bildung abgeschlossen ist;
Lemma E Þ DA enthält die leere Menge, DA enthält alle endlichen Mengen;
Satz D, Satz K Þ DA ist abgeschlossen gegen *-Bildung, Konkatenation und Vereinigung;
Þ RÍDA
Zeige nun die mengentheoretische Inklusion von DA in R ("Ê"):
Beweisidee: Wähle einen beliebigen
endlichen deterministischen Akzeptor (der L(A) erkennt) und konstruiere dazu einen regulären Ausdruck R (mit der Bedeutung s(R)), so daß L(A)=s(R).
Sei A=(X,S, d,1,F) ein
endlicher deterministischer Akzeptor mit n Zuständen (o.B.d.A.: S={1,...,n}).
Beweismethode: Vollständige Induktion über die (Nummern der) Zwischenzustände, die man benötigt, um von einem Zustand i in einen Zustand j zu gelangen.
Definiere für alle i,jÎS und kÎ{0,1,...,n} ( entspricht: kÎ({0}ÈS) ) :
Wijk := { wÎX | d(i,w)=j Ù "u,vÎX*\{e}( w=uv Þ d(i,u)£k ) }
(Wijk sei die Menge aller Wörter mit denen man vom Zustand i in den Zustand j kommt und unterwegs nur über die Zwischenzustände von 1 bis k kommt)
Induktionsanfang: (k=0)
Wij0 Í XÈ{e} ( von i nach j ohne Zwischenzustände Þ |w|=1 oder w=e )
Wij0 kann also durch einen regulären Ausdruck dargestellt werden, nämlich: |
{ | X |
| Æ* |
Induktionsannahme: (k ist eine beliebige natürliche Zahl)
Wir nehmen an, für ein beliebiges k³0 und für alle i,jÎS seien die Mengen Wijk bereits konstruiert und durch einen regulären Ausdruck darstellbar.
Dann gilt für alle i,jÎS:
Induktionsschritt: (zeige "i,jÎ{1,...,n}"kÎ{0,1,...,n}(WijkÎR Þ Wijk+1ÎR) )
Es zeigt sich: Wijk+1 = Wijk È Wi(k+1)k·(W(k+1)(k+1)k)*·W(k+1)jk
Die Menge der Wege von i nach j über die Zwischenzustände 1 bis (k+1) (Wijk+1) setzt sich zusammen aus (trivialerweise) allen Wegen von i nach j über die ersten (k) Zustände (Wijk) UND den Wegen, die tatsächlich den Zustand (k+1) passieren.
Diese Wege kann man als Wegfolgen (Konkatenation einzelner Wegstücke) betrachten, wobei man für den Anfang jeder Wegfolge der Zustand i, für das Ende der Zustand j angenommen wird (es geht ja von i nach j). Zwischendurch jedoch wähle man die Wegstücke so, so daß sie mit dem Zustand (k+1) enden und beginnen. Also vom Zustand i in den Zustand (k+1) gehen (erstes Wegstück), diesen Zustand (k+1) eventuell immer wieder durchlaufen (weitere Wegstücke) und anschließend in den Zustand j gehen (letztes Wegstück) (Wi(k+1)k·(W(k+1)(k+1)k)*·W(k+1)jk).
Die einzelnen Wegstücke haben nur Zwischenstops in Zuständen von 1 bis k.
Und diese Teilstücke (Wijk , Wi(k+1)k , (W(k+1)(k+1)k)* und W(k+1)jk) sind bereits (nach Induktionsannahme) als regulärer Ausdruck dargestellt.
Da auch die Vereinigung, die *-Bildung und die Konkatenation wiederum reguläre Ausdrücke ergeben, ist auch die Folge (Wijk È Wi(k+1)k·(W(k+1)(k+1)k)*·W(k+1)jk) wiederum ein regulärer Ausdruck.
Fazit:
Ist Wijk als regulärer Ausdruck darstellbar, dann ist es auch Wijk+1!
Da wir den Anfang mit k=0 gezeigt haben, gilt dies folglich für alle beliebigen natürlichen Zahlen.
Die akzeptierte Sprache des
Akzeptors L(A) ist folglich die Vereinigung aller Wege vom Startzustand in alle möglichen Endzustände (wobei als Zwischenzustände alle Zustände des
Akzeptors möglich sind):
L(A) = |
È W1jn ; dies ist ebenfalls ein regulärer Ausdruck |
|
jÎF |
Þ L(A)ÎR, für einen beliebigen
endlichen deterministischen Akzeptor A
Þ DAÍR
Dieser Beweis hat einen schönen Nebeneffekt.
Er gibt eine Anleitung, um für jeden
Akzeptor die erkannte Sprache zu ermitteln, indem wir den zugehörigen regulären Ausdruck bestimmen.
In folgendem kleinen Programm ist die Anleitung realisiert:
Programm
Beispiel:
Gegeben sei der
Akzeptor A = ({a,b},{1,2},d,1,{2}) mit folgendem (graphisch dargestellten) d:
dann ist ersichtlich (Betrachtung 1):
W110 = {e}W120 = {a,b}
W210 = {a}W220 = {e,b}
daraus folgt (Betrachtung 2):
W111 = W110 È W110·(W110)*·W110={e}
W121 = W120 È W110·(W110)*·W120= {a,b}
W211 = W210 È W210·(W110)*·W120= {a}
W221 = W220 È W210·(W110)*·W120= {e,b}È{aa,ab}
daraus folgt (Betrachtung 3):
W112 = W111 È W121·(W221)*·W211= {e}È{a,b}{e,b,aa,ab}*{a}
= {e}È{a,b}{b,aa,ab}*{a}
W122 = W121 È W121·(W221)*·W221= {a,b}È{a,b}{e,b,aa,ab}*{e,b,aa,ab}
= {a,b}È{a,b}{e,b,aa,ab}*
= {a,b}È{b,aa,ab}*
W212 = W211 È W221·(W221)*·W211
= {a}È{e,b,aa,ab}{e,b,aa,ab}*{a} = {a}È{b,aa,ab}*
W222 = W221 È W221·(W221)*·W221
= {e,b,aa,ab}È{e,b,aa,ab}{e,b,aa,ab}*{e,b,aa,ab}
= {b,aa,ab}*
nun ergibt sich für die Betrachtung von L(A):
L(A) = |
È W1j2 = W122 = {a,b}È{b,aa,ab}* |
|
jÎF |
ein entsprechender regulärer Ausdruck R ist demnach:
R
= (aÈb)·((bÈ(a·a))È(a·b))*
= (aÈb)((bÈaa)Èab)*