Theoretische Informatik (Vorlesung 9)

3. Grammatiken

• Eine Grammatik G = (N, Σ, S, P)
  • N, Σ sind Alphabete
  • S ist Startsymbol
  • P ist eine Menge von Regeln u → v
  • Erzeugen von Wörtern aus dem Alphabet Σ
  • Sind mächtiger als DEA ( können mehr Sprachen beschreiben )
• Bsp:  
  • G = ({S}, {a,b}, S, P) // G*
  • P = {S → Σ, S → a S b }
  • S Ⱶ_g a S b Ⱶ_g a ( a S b ) b Ⱶ_g a² b²
  • L(G) = { w ∈ Σ*; S Ⱶ_g* w } ist die von G erzeugte Sprache
  • L(G) = { aⁿ bⁿ, n ∈ ℕ }
• Bsp:
  • G = (N, Σ, S, P)  mit N = {S,B} // G**
  • E = {a,b,c}
  • P = {S → a S b c, S → a b c, cB → Bc, bB → bb}
  • L(G) = {aⁿ bⁿ cⁿ, n ∈ ℕ}
• Ziel:
  • Für welche formalen Sprachen ist das Wortproblem entscheidbar?
  • Geg.: L ⊆ Σ*; w ∈ Σ*
  • Frage: Gilt w ∈ L ?

3.1 Chomsky-Hierarchie

• Definition 3.6 Chomsky-Hierarchi für Grammatiken
  • Sei G = (N, Σ, S, P)
  • Jede Grammatik heißt vom Typ 0 ( rekursiv aufzählbar )
  • G heißt vom Typ 1 ( kontextsensitiv ) wenn jede Produktion die Form (schwer)
    • u₁ A u₂ → u₁ w u₂ mit A ∈ N, u₁, u₂, w ∈ (N ∪ Σ)* und |w| ≥ 1 oder
    •  S → E ( dann kommt S in keiner Produktion auf der rechten Seite vor )
• G heißt vom Typ 2 (kontextfrei), wenn jede Produktion die Form ( mittel )
  • A → w mit A ∈ N und w ∈ (N u Σ)*
• G heißt vom Typ 3 (rechtslinear), wenn jede Produktion die Form ( leicht )
  • A → u B mit A,B ∈ N und u ∈ Σ*, oder
  • A → u mit A ∈ N und u ∈ Σ*
• Verschiedene Typen von Grammatiken anhand von Bedingungen an die Form der Produktionen
• Definition 3.7
• kontextsensitiv:
  • u₁ A u₂ → u₁ w u₂ (Ersetzung von A hängt vom Kontext ab. Links muss u₁ und rechts u₂ stehen)
  • Bsp:
    • cB → Bc
    • bB → bb
    • = B kann nur dann ersetzt werden, wenn links c oder b steht
  • Bedingung:
    • |w| ≥ 1 sorgt dafür, dass Wörter während des Ableitungsprozesses nicht kleiner werden.
    • S → Σ ist zwar erlaubt, aber S darf dann nicht auf der rechten Seite einer Produktion vorkommen. Die Regel kann also nur genutzt werden um E abzuleiten. ← gilt für kontextsensitive
• kontextfrei
  • A → w ( A kann unabhängig davon, was links oder rechts von A steht ersetzt werden )
  • Bsp. 3.8: Die Grammatik * ist kontextfrei ( und auch rekursiv abzählbar, aber weder rechtslinear, noch kontextsensitiv )
  • Die Grammatik ** ist kontextsensitiv ( und rekursiv abzählbar, aber nichts rechtslinear und nicht kontextfrei )
  • Die Grammatik *** ist rechtslinear, kontextfrei, rekursiv abzählbar, aber nicht kontextsensitiv ( wegen B → E )
  • Bsp. 
    • G = (N, Σ, S, P) mit //G***
      • N = {S,B}
      • E = {a,b}
      • P = { S → aS|bS|abB, B → aB|bB|E}
• Definition 3.9:
  • Eine Sprache L heißt rechtslinear ( kontextfrei, kontextsensitiv, rekursiv abzählbar), wenn es eine rechtslineare (kf, ks, ra) Grammatik G mit L = L(G) gibt.
  • Sei ℒ₁ ( altdeutsches L ) = { L(G); G ist eine Typ – 1 Grammatik}
  • ℒ₃ = Menge aller rechtslinearen Sprachen
  • ℒ₃ ⊂ ℒ₂
  • ℒ₁ ⊂ ℒ₀
  • Frage: Gilt ℒ₂ ⊂ ℒ₁
  • Wir werden noch sehen ℒ₂ ⊂ ℒ₁ ( und damit ℒ₃ ⊂ ℒ₂ ⊂ ℒ₁ ⊂ ℒ₀)
• Wir stellen uns die folgenden Kernfragen:
  • Bilden diese Sprachklassen eine echte Hierarchie (d.h. sind alle Inklusionen echt) → Ja ( sog. Chomsky-Hierarchie )
  • Gibt es andere Charakterisierungen, z.B. über Automaten? → Ja

Grammatik	Automaten/Maschinen
ℒ0	Turingmaschinen
ℒ1	Linear beschränkte Automaten ( beschränkte Turingmaschinen)
ℒ2	Kellerautomaten (DEA mit zusätzlichem Speicher)
ℒ3	DEA

• Bezüglich welcher Operationen ( Vereinigung, Schnitt, Komplement ) sind diese Klassen abgeschlossen? → Das Verhalten ist sehr unterschiedlich.
• Kann man auf einfachere Regelformen reduzieren (Normalform) → Ja, für kontextfreie werden wir das untersuchen
• Wie verhalten sich die Entscheidungsprobleme Wort-, Äquivalenz- und Leerheitsproblem? → Das Verhalten ist sehr unterschiedlich. 

3.2 Grammatiken und das Wortproblem

• Wortproblem ( L ⊆ Σ* )
  • Gegeben: w ∈ Σ*
  • Frage: Gilt w ∈ L
• Wir suchen einen Algorithmus, der 
  1. bei jeder Eingabe terminiert
  2. die richtige Antwort liefert
• Algorithmus für das Wortproblem für DEAs
  • Eingabe: w ∈ Σ*; DEA A = (Q, Σ, q₀, δ, F)
  1. q = δ*(q₀, w)
  2. IF q ∈ F then Return wahr else return falsch
• Algorithmus für das Wortproblem für Grammatiken
  • Eingabe: G = ( N, E, S, P ) und w ∈ Σ*
  • Beachte Algorithmus aus Script! Besser!
  1. Erzeuge die Wörter von L(G) schrittweise durch Ableiten
  2. Prüfe, ob w erzeugt wurde.
  3. Wenn ja, gib wahr aus und stoppe.
  4. Wenn nein, gehe zu 1. ← Suboptimal mit vielen Durchläufen
  • Wenn w ∈ L(G), dann wird w irgendwann erzeugt und der Algorithmus terminiert mit wahr.
  • Wenn w ∉ L(G), dann wird w nicht erzeugt und der Algorithmus terminiert nicht. ( somit nur Semi-Entscheidbar )
    • Über das Komplement ¬G = L(¬G) = ¬(L(G)) könnte man herangehen. 
  • Somit brauchen wir eine Abbruchbedingung.