Chomsky Hierarchie

Typ 2 - kontextfreie Grammatik

• Eigenschaften:
  • linke Seite: ein Nichtterminalsymbol
  • rechte Seite: eine beliebige Zeichenkette aus Terminal- und Nichtterminalsymbolen, Möglichkeit einer leeren Zeichenkette
  • Darstellung beispielsweise durch EBNF oder Syntaxdiagramme
  • Erkennung durch Kellerautomaten
  • Festlegung von kontextfreien Sprachen
• Mächtigkeit:
  • Die kontextfreie Grammatik ist durch die Unabhängigkeit vom Kontext begrenzt, weshalb keine Bedingungen für Nichtterminalsymbole formuliert werden können.
• Kellerautomat (PDA, engl.: Pushdown Automaton):
  • Ein PDA ist ein Septupel: M = (Q, Σ, Γ, δ, q₀, E, Z)
    • Q: endliche Menge von Zuständen
    • Σ: Eingabealphabet
    • Γ: Kelleralphabet
    • δ: totale Überführungsfunktion, Q × Σ ⟶ Q
    • q₀: Anfangszustand, q₀ ∈ Q
    • E: endliche Menge an Endzuständen, E ⊆ Q
    • Z: Anfangssymbol im Keller, Z ∈ Γ
  • deterministischer Kellerautomat (DPDA) und nichtdeterministischer Kellerautomat (NPDA) möglich
  • Besitzen eines Stacks (dt.: Keller) zum Speichern von Werten ⟶ LIFO-Prinzip
  • Schreibweisen, mit q_alt = alter Zustand, q_neu = neuer Zustand, z = eingelesenes Zeichen, pop = aus dem Stack entnommener Wert, push = in den Stack geschriebener Wert:
    • Verarbeitungsschritte: "q_alt, z, pop ⟶ q_neu, push"
    • Zustandsübergänge im Kellerautomaten: "z, pop; push"
• Beispiel zur Erkennung von Palindromzahlen mit dem Alphabet {0,1}:
  • Grammatik:

    G = {V, Σ, P, S}
    V = {Palindromzahl, Ziffer}
    Σ = {'0', '1'}
    P = {Palindromzahl = Ziffer | '0' [Palindromzahl | Ziffer] '0' | '1' [Palindromzahl | Ziffer] '1';
         Ziffer = '0' | '1'}
    S = {Palindromzahl}
    

  • Automat:
    

    Hierbei ist λ (oder ε) das leere Wort und Z (oder #) das Anfangssymbol des Kellers. Der Automat kann so lange im Zustand q0 bleiben und die Ziffern in den Stack schreiben, bis er die Mitte der Palindromzahl erreicht. Bei einer ungeraden Anzahl an Ziffern geht er mit der nächsten eingelesenen Ziffer in den Zustand q1 über und bei einer geraden Anzahl an Ziffern geht er ohne weiteren eingelesenen Wert über. Im Zustand q1 kann der Automat die geschriebenen Ziffern wieder entfernen, solange die Eingabe eine Palindromzahl ist. Wenn die Eingabe keine Palindromzahl ist, wird er Stack nie leer und der Automat kann nicht in den Endzustand q2 übergehen.