Achtung : Skript  abgeschlossen
                  

1. Einführung

Das Ziel der heutigen Vorlesung ist die Beweisführung, dass die Menge der regulären Sprachen LREG, die von regulären Grammatiken (Chomsky Hierarchie Typ3) definiert werden, identisch ist, mit der Menge der Sprachen LDFA, die von einem deterministischen endlichen Automaten DFA erkannt wird. Ferner wird gezeigt, dass die Sprachen LNFA, die von einem nichtdeterministischen Automaten NFA erkannt werden können, die gleichen sind, wie die Sprachen LDFA. Bevor diese Beweise geführt werden, werden zunächst Beispiele für alle beteiligten Begriffe gegeben.

2. Beispiel einer reglären Grammatik und Sprache

Es wird jetzt das Beispiel einer regulären Grammatik g4 im Format einer rechtslinearen Grammatik gegeben, die die folgende Sprache definiert: L(g4,3) = {anne, anke, abzug, ablage}

FG(g4,3) mit g4 = < <V_g4,T_g4,S_g4 > P_g4>

mit

V_g4 = {S, X, Y, Z, G, H, M, V}

T_g4 = {a, b, e, g, k, l, n, u, z}

P_g4 = {(S,aX), (X,bY),(X,nZ),(Y,zV),(Y,lW),(V,uM),(W,aG),(G,gH),(Z,nG),(Z,kG),(M,g),(H,e)}

Vereinbarungsgemäss kann man statt (S,aX) auch schreiben S ---> aX und statt '(X,bY),(X,nZ)' kann man auch schreiben X --> bY | nZ.

Laut Definition ist ein Wort w dann in der Sprache L(g4,3) wenn w in g4 ableitbar ist, also S_g4 *=>_g4 w, und g4 ist eine formale Grammatik vom Typ3, also FG(g4,3). Man müsste also zeigen, dass die Worte {anne, anke, abzug, ablage} alle ableitbar sind und auch nur genau diese.

Eine Möglichkeit, dies zu tun besteht darin, dass man bezogen auf den Syntaxbaum ein allgemeines Verfahren (Algorithmus) definiert, das diesen Baum systematisch absucht. Ein Verfahren wäre das folgende (informelle Beschreibung):

1. Beginne bei dem Wurzelknoten S

2. Markiere letzten Knoten und gehe zum nächsten. Wenn es Alternativen gibt, wähle den am weitesten links liegenden Knoten.

3. Ist der Pfad zu Ende ohne ein terminales Element, dann Fehlermeldung

4. Andernfalls gebe den Pfad aus.

5. Backtracking: suche rückwärts den nächsten noch nicht markierten Pfad

6. Falls es keinen mehr gibt: Ende

7. Andernfalls setze fort bei 2

Wenn dieses Verfahren keine Fehlermeldung produziert, dann generiert es die Menge aller möglichen Pfade. Hier ein Beispiel für Ableitungen nach diesem Verfahren:

1. S (S ---> aX)

2. aX (X ---> bY)

3. abY (Y ---> zV)

4. abzV (V ---> uM)

5. abzuM (M ---> g)

6. abzug

Ein Pfad im Syntaxbaum ist jetzt markiert. Mittels Backtracking wird jetzt rückwärts nach einer möglichen Fortsetzung gesucht. Diese ist hinter dem Knoten 'bY' gegeben. Es wird also hier eine zweite Ableitung versucht:

1. S (S ---> aX)

2. aX (X ---> bY)

3. abY (Y ---> lW)

4. ablW (W ---> aG)

5. ablaG (G ---> gH)

6. ablagH (H ---> e)

7. ablage

Entsprechend leitet man die beiden restlichen Worte 'anne' und 'anke' ab. Das Verfahren stoppt an dieser Stelle, da alle Knoten markiert sind. Auserdem wurde keine Fehlermeldung ausgegeben. Also wurden genau die Worte erzeugt, die die Sprache definieren. Damit wäre nun ein Beispiel für eine reguläre Grammatik und der durch sie definierten Sprache gegeben. Im nächsten Beispiel wird gezeigt, wie ein endlicher deterministischer Automat eine solche reguläre Sprache erkennen kann.

Man überzeuge sich an diesem Beispiel auch davon, dass die Verwendung einer linkslinearen statt einer rechtslinearen Form am Ergebnis nichts ändern würde.

3. Beispiel eines deterministischen endlichen Automaten

Zunächst wird an einem konkreten Beispiel informell gezeigt, wie man, ausgehend von einer regulären Grammatik, einen deterministischen endlichen Automaten konstruieren kann, der genau diese Sprache erkennt. Anschliessend ird dies in allgemeiner Form bewiesen.

Den Ausgangspunkt für die Konstruktion eines konkreten deterministischen endlichen Automaten a4 auf der Basis der Grammatik g4 bilden die folgenden Annahmen:

1. Jede Regel (u,w) in P_g4 mit der Form A ---> a mit A in V_g4 & a in T_g4 wird übersetzt < A,a,q> in P_a4 mit q in E_a4

2. Jede Regel (u,w) in P_g4 mit der Form A ---> aB mit A,B in V_g4 & a in T_g4 wird übersetzt < A,a,B> in P_a4

3. Q_a4 = V_g4

4. q₀ = S_g4

5. E_a4 ist die Menge aller q in < A,a,q>, die aus A ---> a hervorgegangen sind. Es soll '1' den akzeptierenden Endzustand bezeichnen, also 1 in E

Mit diesen Annahmen kann man jetzt die Grammatik g4 direkt in einen Automaten a4 übersetzen, nämlich:

a4 = < <Q_a4, T_a4, {q₀}, E_a4 > P_a4> mit

1. <S,a,X>

2. <X,n,Z>

3. <X,b,Y>

4. <Y,lW>

5. <Y,z,V>

6. <W,a,G>

7. <G,g,H>

8. <H,e,1>

9. <V,u,M>

10. <M,e,1>

11. <Z,n,H>

12. <Z,k,H>

Ob der Automat die Sprache L(g4,3) = {anne, anke, abzug, ablage} erkennt oder nicht, kann man informell am Zustandsgraphen überprüfen, indem man ein Wort x aus L(g4,3) nimmt, z.B. x = anne. Da es ausgehend von S eine Ereigniskette 'a', 'n', 'n' und 'e' entlang der Zustände S, X, Z,H gibt, die im Endzustand E endet, gilt, dass der Automat das Wort x=anne erkennt.

Mithilfe des Ableitungsbegriffs von a4 kann man dies auch ganz formal durchspielen. Wegen

x in T(a4) gdw x in {w | w in T_a4* & P_a4'(q₀,w) in E_a4 }

gilt also, das x=anne genau dann ein Wort von T(a4) ist, wenn w ein Wort über dem terminalen Alphabet T_a4 von a4 ist und die Anwendung von P_a4' auf w einen Zustand ergibt, der ein Endzustand ist. Konkret, da q₀ = S, gilt (für die Definition von P'() siehe VL8):

1. P'(S,anne)

2. P'(P(S,a),nne)

3. P'(X,nne)

4. P'(P(X,n),ne)

5. P'(Z,ne)

6. P'(P(Z,n)e)

7. P'(H,e)

8. P'(P(H,e),§)

9. P'(1,§)

10. 1

Man sieht, dass es eine Ableitung gibt, die im Zustand 1 endet, wobei 1 ein Endzustand ist. Statt dies jetzt für alle Einzelfälle durchzuspielen, beweisen wir jetzt einen allgemeinen Satz.

4. Satz: jede reguläre Sprache wird durch einen DFA erkannt

Wir wollen jetzt ganz allgemein beweisen, dass jede reguläre Sprache durch einen deterministischen Automaten erkannt wird. Formal sieht der Satz folgendermassen aus:

(A:l,g)( l = L(g,3) ==> (E:a)( DFA(a) & l = T(a) ))

Für alle l, die einer durch eine formale Grammatik g vom Typ 3 ableitbare Sprache entsprechen, gibt es einen deterministischen endlichen Automaten a und l entspricht der durch a erkennbaren Sprache T(a).

Angenommen also, wir haben ein l = L(g,3)

Dann gilt, dass ein x in l gdw wenn x in L(g,3)

Dann gilt, dass ein x in L(g,3) gdw ABL(x,S_g,g) & FG(g,3)

Dann gibt es ein g = < <V_g,T_g,S_g > P_g>

Ausgehend von g kann man dann ein a' definieren, das die folgenden Eigenschaften hat:

1. a' = < <Q_a', T_a', {q₀}, E_a' > P_a'> mit

2. Q_a' = V_g

3. T_a' = T_g

4. q₀ = S_g

5. P_a' wird aus P_g dadurch gebildet, dass man für alle (u,w) in P_g setzt:

1. wenn w = a (a in T_g), dann < u,w,e> in P_a' mit e in E_a'

2. wenn w = aB (a in T_g, B in V_g), dann < u,w,B> in P_a'

Aus ABL(x,S_g,g) folgt, dass es eine endliche Ableitung der folgenden Art gibt, wobei wir annehmen x=a₁a₂...a_n-1a_n

• S_g

• a₁V₁

• a₁a₂V₂

• ...

• a₁a₂...a_n-1V_n-1

• a₁a₂...a_n-1a_n

Dies bedeutet, ausgehend vom Startsymbol S_g wird durch Anwendung von Regeln aus g eine endliche Ableitung erzeugt, an deren Ende die Zeichenkette x steht.

Aus a' folgt, dass man zu jeder solchen Ableitung auch eine Ableitung mittels P_a' sowie mittels P_a'' erzeugen kann. Sei x=a₁a₂...a_n-1a_n wie oben, dann gilt:

• P'(q₀,a₁a₂...a_n-1a_n)

• P'(P(q₀,a₁),a₂...a_n-1a_n)

• P'(q₁,a₂...a_n-1a_n)

• P'(P(q₁,a₂),...a_n-1a_n)

• P'(q₂,a₃...a_n-1a_n)

• ...

• P'(P(q_n-1,a_n),§)

• P'(q_n,§)

• q_n

Da jede Regel von P_g nach P_a' abgebildet wurde, gibt es, beginnend mit q₀, Regeln, die sich auf q₀ und dann auf die Folgezustände anwenden lassen. Denn, entweder handelt es sich um eine Regel aus A ---> aB, dann führt P(A,a) in den Folgezustand B, oder aber es handelt sich um eine Regel aus A ---> a, dann gilt, dass P(A,a) auf einen Folgezustand e führt, der aus den Endzuständen E_a' stammt. Der Fall P'(q_n-1,a_n) beschreibt genau dieses, denn hinter a_n kommt kein weiteres Zeichen; dies entspriicht der Regel V_n-1 ---> a_n, d.h. P'(P(q_n-1,a_n),§) erzeugt einen Folgezustand q_n, der zu E_a' gehört,

also wurde die Eingabe x erkannt, .

d.h. w in L(g,3) ==> x in T(a')

Da man jede Ableitung, die zu T(a') führt, auch in eine Ableitung umformen kann, die zu L(g,3) führt, folgt weiter:

x in T(a') ==> x in L(g,3)

also L(g,3) = T(a')

also l = T(a')

also (E:a)( DFA(a) & l = T(a) )

also l= L(g,3) ==> (E:a)( DFA(a) & l = T(a) )

also (A:l,g)( l= L(g,3) ==> (E:a)( DFA(a) & l = T(a) ))

5.Satz: L(g,3) C T(a)

Wie man aus dem vorausgehenden Beweis sieht, kann man auch noch einen viel kompakteren Satz beweisen, nämlich dass jede durch eine formale Grammatik g vom Typ3 erzeugbare Sprache eine Teilmenge der Sprachen ist, die von einem deterministischen Automaten a erkannt werden. Ausführlich:

(A:g,a)( L(g,3) C T(a) )

Anders geschrieben: (A:x)( x in L(g',3) ==> x in T(a') )

Angenommen also: x' in L(g',3)

Dann: x' in L(g',3) gdw ABL(x',S_g,g) & FG(g',3)

Analog zum vorausgehenden Beweis kann man dann aufgrund der Existenz einer formalen Grammatik g' einen deterministischen endlichen Automaten a' definieren.

Aus der Existenz von a' ergibt sich dann eine Ableitung mit P'_a für x'

also x' in T(a')

dann x' in L(g',3) ==> x' in T(a')

dann (A:x)( x in L(g',3) ==> x in T(a') )

dann L(g',3) C T(a')

dann (A:g,a)( L(g,3) C T(a) )

6. Satz: T(a)C L(g,3)

Jetzt sollte auch schon klar sein, wie man die Umkehrung des vorausgehenden Satzes beweisen kann, nämlich dass jede von einem deterministischen Automaten a erkannte Sprache auch eine reguläre Sprache ist, formal:

(A:a,g)( T(a)C L(g,3))

Anders geschrieben: (A:x)( x in T(a') ==> x in L(g',3) )

Angenommen also: x' in T(a')

Dann: x' in T_a'* & DFA(a') & P'_a'(q₀,x') in E_a'

Auf der Basis von DFA(a') kann man dann eine formale Grammatik g' definieren.

Aus der Existenz von g' folgt dann die Existenz einer Ableitung ABL(x',S_g',g')

Also: x' in L(g',3)

Also: x' in T(a') ==> x' in L(g',3)

Also: (A:x)( x in T(a') ==> x in L(g',3) )

Also: T(a')C L(g',3)

Also: (A:a,g)( T(a)C L(g,3) )

7. Satz: T(a)= L(g,3)

Aus den beiden vorausgehenden Sätzen ergibt sich jetzt der Satz, dass die Menge der durch einen deterministischen Automaten erkennbaren sprachen identisch ist mit der Menge der durch eine reguläre Grammatik erzeugbarenb Sprachen, 'direkt':

(A:a,g)( T(a)= L(g,3) )

8. Beispiel für eine reguläre Grammatik g5

Es wird jetzt das Beispiel einer regulären Grammatik g5 im Format einer rechtslinearen Grammatik gegeben, die die gleiche Sprache wie die Grammatik g4 definiert: L(g5,3) = {anne, anke, abzug, ablage}. Trotzdem unterscheidet sich die Grammatik g5 von der Grammatik g4 durch die benutzten Regeln:

FG(g5,3) mit g5 = < <V_g5,T_g5,S_g5 > P_g5>

mit

V_g5 = {S, X₁, X₂, Y₁, Y₂, Z₁, Z₂, G, H, M, V}

T_g5 = {a, b, e, g, k, l, n, u, z}

P_g5 = {(S,aX₁),(S,aX₂),(X₁,bY₁),(X₁,bY₂),(X₂,nZ₁ ),(X₂,nZ₂), (Ysub>1,zV),(Y₂,lW),(V,uM), (W,aG),(G,gH),(Z₁,nG),(Z₂,kG),(M,g),(H,e)}

Man sieht, dass durch die Änderung der Produktionsregeln von g5 zusätzliche Alternativen entstehen.

Für die Ableitung (bzw. Erzeugung) von Worten mit der Grammatik g5 gelten die gleichen Regeln wie oben im Fall der Grammatik g4. Das Hauptaugenmerk liegt in diesem Fall darauf, aus der Grammatik g5 einen nichtdeterministischen endlichen Automaten a5 zu konstruieren.

9. Beispiel für einen nichtdeterministischen endlichen Automaten zur Grammatik g5

1. Jede Regel (u,w) in P_g5 mit der Form A ---> a mit A in V_g5 & a in T_g5 wird übersetzt < A,a,{q}> in P_a5 mit q in E_a5

2. Jede Regel (u,w) in P_g4 mit der Form A ---> aB₁ | ... | aB_n mit A,B_i in V_g5 & a in T_g5 wird übersetzt < A,a,{B₁, ..., B_n}> in P_a5

3. Q_a5 = V_g5

4. S_a5 = S_g5 /* a5 hat eine Menge von Anfangszuständen ! */

5. E_a5 ist die Menge aller q in < A,a,{q}>, die aus A ---> a hervorgegangen sind. Es soll '1' den akzeptierenden Endzustand bezeichnen, also 1 in E

Mit diesen Annahmen kann man jetzt die Grammatik g5 direkt in einen Automaten a5 übersetzen, nämlich:

a5 = < <Q_a5, T_a5, S_a5, E_a5 > P_a5> mit

Ob der Automat die Sprache L(g5,3) = {anne, anke, abzug, ablage} erkennt oder nicht, kann, analog wie im obigen Beispiel mit dem endlichen Automaten a4, wieder informell am Zustandsgraphen überprüfen, indem man ein Wort x aus L(g5,3) nimmt, z.B. x = anne. Da es ausgehend von S eine Ereigniskette 'a', 'n', 'n' und 'e' entlang der Zustände S, X₂, Z₁,H gibt, die im Endzustand 1 endet, gilt, dass der Automat das Wort x=anne erkennt.

Mithilfe des Ableitungsbegriffs von a5 kann man dies auch ganz formal durchspielen. Wegen

x in T(a5) gdw x in {w | w in T_a5* & P_a5'(S_a5,w) cut E_a5 != 0 }

gilt also, das x=anne genau dann ein Wort von T(a5) ist, wenn w ein Wort über dem terminalen Alphabet T_a5 von a5 ist und die Anwendung von P_a5' auf w eine Menge von Zuständen ergibt, von denen mindestens einer ein Endzustand ist. Konkret, da S_a5 = S, gilt (für die Definition von P'() siehe VL8):

1. P'({S},anne)

2. P'({P(S,a)},nne)

3. P'({X₁,X₂ },nne)

4. P'({P(X₁,n), P(X₂,n) },ne)

5. P'({Z₁, Z₂ },ne)

6. P'({P(Z₁,n), P(Z₂,n) },e)

7. P'({H},e)

8. P'({P(H,e)},§)

9. P'({1},§)

10. 1

11. 1 in E_a5

Man sieht, dass es eine Ableitung gibt, die in einem Zustand 1 endet, wobei 1 ein Endzustand ist. .

10. Testfragen

Werden in der Übung gegeben.

START