Theoretische Informatik (Vorlesung 12)

Chomsky-Normalform

• Eine kontextfreie Grammatik G = (N, Σ, S, P) liegt in Chomsky-Normalform vor, falls jede Produktion die Form
  • A → a mit A ∈ N und a ∈ Σ oder
  • A → BC mit A, B, C ∈ N

t_1n

• Die Menge der NTS von denen sich das Teilwort von w, das an erster Stelle beginnt und Länge n hat, ableiten lässt ( t_1n =  w )
• Dann gilt w ∈ L(G) (S|-_g* w ) → S ∈ t_1n.
• Wie konstrukiert man t_1n in endlichen Schritten?
  1. Bestimme t₁₁, t₂₁, t₃₁, .. , t_n1 (t₁₁ ist die Menge aller NTS von denen aus sich das Teilwort von w, das an erster Stelle beginnt und Länge 1 hat) ableiten lässt ( w=w₁ .. w_n ) t₁₁ = { A ∈ N, A → w₁ ∈ P} t₂₁ = { A ∈ N, A → w₂ ∈ P} … t_n1 = { A ∈ N, A → wn ∈ P}
• Wie bestimmen wir t_ik für k>=2?
  • t_ik = { A ∈ N, es existiert ein z ∈ { 1,…, k-1} und B,C ∈ N so, dass A → BC ∈ P, B,C ∈ N so, dass A → BC ∈ P, B |-_g* w_i .. w_{(i + z -1)} und C |-_g* w_(i+z) … w_(i+k-1)
  • B |-_g* w_i .. w_(i+z-1) ↔ B ∈ t_iz und C |-_g* w_(i+z) .. w_i+k-1 ↔  C ∈ t_{(i+z, k-z)} also
  • t_ik = { A ∈ N, es ex. z ∈ { 1,..,k-1} und B,C ∈ N so, dass A → BC ∈ P, B ∈ t_iz und C ∈ t_{(i+z, k-z)} , also = U^(k-1)__z=1 { A ∈ N, € B,C ∈ N mit A → BC  ∈ P, B ∈ t_iz und ( ∈ t_(i+z,k-z) )
• Algorithmus CYK-Algorithmus Eingabe: Eine kontextfreie Grammatik G = (N, Σ, S, P) in Chomsky-Normalform, ein Wort w ∈ Σ*

1. n := |w|
2. for i = 1 to n do
3. t_i1 = {A ∈ N; A −→ w_i ∈ P}
4. od // od = end // Wir wandeln das Wort in einzelne Zeichen um und leiten diese in NTS zurück ab
5. for k = 2 to n do
6. for i = 1 to n − k + 1 do
7. t_ik = ∅
8. for z = 1 to k − 1 do // Wir laufen mit größer werdendem Bereich, beginnend bei 2 durch das Wort, erzeugen dabei Teilworte und schauen, ob die Paare von einem einzelnen NTS erzeugt werden können
9. tik = tik ∪ {A ∈ N; ∃B, C ∈ N : A −→ BC ∈ P, B ∈ t_iz, C ∈ t_i+z,k−z }
10.  od
11.  od
12.  od
13.  if S ∈ t_1n then
14. return wahr
15. else
16. return falsch
17. fi

• Satz 3.17.
  • Das Wortproblem fur kontextfreie Sprachen, die durch Grammatiken in Chomsky  -Normalform gegeben sind, sind in Zeit O(n³) entscheidbar
•  Beispiel 3.18.
  • Wir betrachten die Grammatik G = (N, Σ, S, P) mit N = {A, B, C, S}, Σ = {0, 1} und den Produktionen
    • S → AC,
    • S → AB,
    • C → SB,
    • A → 0,
    • B → 1
    • Für das Wort w = 0011 ∈ Σ* wollen wir überprüfen, ob w ∈ L(G). Dazu berechnen wir wie der CYK-Algorithmus die Menge t_1n.
    • w = 0011
    1. n = 4
    2. t₁₁ = { x ∈ N; x → w₁ ∈ P } = { x ∈ N; x → 0 ∈ P } = { A } // =0 t₂₁ = { x ∈ N; x → w₂ ∈ P } = { x ∈ N; x → 0 ∈ P } = { A } // =0 t₃₁ = { B } t₄₁ = { B } 
    3. t₁₂ = U^{2-1_z = 1 =  { X ∈ N; E Y,Z ∈ N mit X → YZ ∈ P, Y ∈ t_iz und Z ∈ t_(i+1,1)} = { X ∈ N,E Y,Z ∈ N mit X→ YZ ∈ P, Y ∈ t₁₁ und z ∈ t₂₁ } = { X ∈ N,E Y,Z ∈ N mit X → YZ ∈ P, Y ∈ { A }, Z ∈ { A } } → Gibt es eine Regel x → AA? → Nein → = Ø} t₂₂ = [ … ] = Regel S → AB der Form X → AB)

tik	K=1	k=2	K=3	k=4
i = 1	A	Ø	Ø	S (t14 = t1n)
i =2	A	S	C	–
i =3	B	Ø	–	–
i =4	B	–	–	–

Chomsky-NF

• A → BC
• A → a
• Typ 0: rek. abzählbar
• Typ 1:KS
  • u₁ A u₂ → u₁ l u₂ mit |l| >=1,0
  • S → E, dann darf S auf keiner rechten Regelseite vorkommen
• Typ 2:KF
  • A → l mit A ∈ N und l ∈ ( N u E)*
• Typ 3: RL

• rechtslinear → kontextfrei
• kontextsensitiv → rek. abzählbar
• kontestfreie Sprache → kontextsensitive Sprache // Gilt nicht für Grammatiken
• Satz 3.19.
  • Zu jeder kontextfreien Grammatik G = (N, Σ, S, P) gibt es eine kontextfreie Grammatik G′ = (N, Σ, S, P) ohne Regeln der Form A → E mit L(G′) = L(G)\{E} // Wir erzeugen die gleiche Sprache ohne das leere Wort
• Satz 3.20.
  • (i) Zu jeder kontextfreien Grammatik G gibt es eine kontextfreie Grammatik G′, in der es keine Regeln der Form A → E für A ≠ S gibt. Ist S → E eine Regel in G′, so kommt S nicht auf der rechten Seite einer Regel in G′ vor. //( mit L(G)\{E} = L(G‘)}
  • (ii) Jede kontextfreie Sprache ist auch kontextsensitiv (d.h. L₂ ⊆ L₁)
• Beweis 3.20
  • (i) Wir konstruieren aus G wie in Satz 3.19 zunachst eine kontextfreie Grammatik G′ ohne Regeln der Form A → E mit  L(G)\{E} = L(G‘)}
  • Ist nun E ∈ L(G), so führen wir ein neues NTS S‘ zu G‘ hinzu, ersetzen in allen Regeln aus G‘ S durch S‘ und fügen die Regeln S → S‘ und S→E zu G‘ hinzu. Die so definierte Grammatik erfüllt dann die Behauptung.
• Beweis 3.19 
  • Sei N_ε = { A ∈ N; A |-_g* E }
  • P‘ = { A → l‘; € A → l ∈ P und l‘ entsteht aus l durch Streichung beliebig vieler NTS B ∈ N_ε }
  • P‘ = { A → ε, A ∈ N } dann erfüllt G = ( N, Σ, S, P ) die Bedingung
  • → Beispiel 3.21 im Skript 
    • → N_ε = {C,A}
    • S → ACB und A→C und C→E zusammenfassen [ S → AB, S→CB und S→B ]
    • C → E

Herleitung Chomsky NF

• Sei also ab jetzt G = (N, Σ, S, P) eine kontextfreie Grammatik ohne Regeln der Form A → ε
• Ziel: Konstruiere aus G eine Grammatik G‘ in Chomsky NF
• Bsp.: G = (N = {S, A, B, C}, Σ = {a, b}, S, P)
  • mit den Produktionen
    • S → ab|aA|A
    • A → B|C|aBb
    • B → S
    • C → abS
• 1. Schritt: Die Nichtterminalsymbole S, A, B sind also gleichwertig (von jedem dieser Nichtterminalsymbole aus lassen sich in der Grammatik wegen des Zyklus die selben Worter ableiten). Wir können also S = A = B setzen und passen die Regeln entsprechend an. Dies führt zu den Produktionen
  • S → ab|aS|S
  • S → S|C|aSb
  • S → S
  • C → abS
  • Zusätzlich können wir die Produktion S → S streichen und erhalten somit die Produktionen
    • S → ab|aS|C|aSb
    • C → abS // wird im nächsten Schritt weggekürzt, da S → C → abS eindeutig ist
• 2. Schritt:Regeln der Form A → B weiter untersuchen und die rechte Regelseite durch lange rechte Regelseiten aus den Regeln B → l mit |l| ≥ 2 ersetzen. In unser Beispielgrammatik gibt es nur noch eine Regel von dieser Form (S → C).
  • S → C => S → abS und erhalten damit S → ab|aS|aSb und  C → abS
• 3. SchrittIn den Regeln der Form A → l mit |l| ≥ 2 ersetzen wir jedes Terminalsymbol a ∈ Σ durch ein zusatzliches Nichtterminalsymbol H_a und nehmen die Regel H_a→ a auf.
  • S → ab =>
    • S→ H_a H_b
    • H_a → a
    • H_b → b
  • S → aS =>
    • S → H_a S
  • S→ abS =>
    • S → H_a H_b S // im nächsten Schritt auf Länge 2 bringen
  • S → aSb =>
    •  S → H_a S H_b // im nächsten Schritt auf Länge 2 bringen
  • C → abS =>
    • C → H_a H_b S // im nächsten Schritt auf Länge 2 bringen
• 4. Schritt Für jede Regel der Form A → l mit |l| ≥ 3 (und damit, wie wir oben gesehen haben besteht l nur noch aus Nichtterminalsymbolen, es gilt also l = A₁ … A_n mit A₁, . . . , A_n ∈ N und n ≥ 3) ersetzen wir sukzessive A₁A₂ durch V (V ist ein neues Nichtterminalsymbol), streichen A → A₁ … A_n und führen die neuen Regeln A → VA₃ .. V_n und V → A₁A₂zu P hinzu. Dies wird solange durchgeführt, bis es keine Regeln der Form A → l mit |l| ≥ 3 mehr gibt.
  • S→ H_a H_b
  • H_a → a
  • H_b → b
  • S → H_a S
  • S → V₁ S, V₁ →  H_a H_b
  • S → V₂ H_b, V₂ → H_a S
  • C → V₃ S, V₃ → H_a H_b
• Satz 3.23 Das Wortproblem für KF-Sprachen ist entscheidbar.
• Beweis: 
  • 1. Prüfe ob ε ∈ L(G) ( Prüfe ob S ∈ N_ε (vgl. Beweis von Satz 3.19))
  • 2. Konstruiere eine Grammatik G‘ ohne Regeln der Form A → ε mit L(G) \ {ε} = L(G‘) ( wieder mit Satz 3.19 )
  • 3. Konstruiere aus G‘ eine Grammatik G‘ in Chomsky NF mit L(G‘) = L(G“)
  • 4. Wende den CYK – Algorithmus auf G“ an