Beispiel 11.3.1 (Kontextfreie Grammatik (CFG, context free grammar)).

• G₁ = ⟨{S,NP,V P,EN,V,D,N},{Egon,Pudel,den,sah},R,S⟩
• Regelmenge

Definition 11.3.2 (Kontextfreie Grammatik). Eine Kontextfreie Grammatik G = ⟨Φ,Σ,R,S⟩ besteht aus:

1. Nichtterminalsymbolen Φ
2. Terminalsymbolen Σ
3. Regelmenge R ⊆ Φ × Γ^∗ (mit Γ = Φ ∪ Σ)
4. Startsymbol S ∈ Φ

Definition 11.3.3 (Direkte (oder unmittelbare) Ableitungsrelation).

• Sei G = ⟨Φ,Σ,R,S⟩ eine Grammatik.
• Seien u und v Folgen von Grammatiksymbolen, d.h. u,v ∈ Γ^∗.
• Dann gilt: v ist aus u direkt ableitbar (u ⇒ v), falls
  • es eine Regel der Form w → z gibt in R
  • und u als Konkatenation u = u₁ ∙ w ∙ u₂
  • und v als Konkatenation v = u₁ ∙ z ∙ u₂ ausgedrückt werden kann.

Definition 11.3.4 (Ableitung (derivation)). Eine Ableitung ist ein n-Tupel ⟨w₁,…,w_n⟩ von Zeichenketten w_i ∈ Γ^∗ mit (1 ≤ i ≤ n) , so dass gilt:

• w_i−1 ⇒ w_i für alle i ∈{2..n}

Definition 11.3.5 (Ableitungsrelation (derivation relation)). Die Ableitungsrelation ist die reflexiv-transitive Hülle von ⇒. Sie verbindet alle Folgen von Symbolen, welche direkt oder indirekt voneinander abgeleitet werden können.

Beispiel 11.3.6 (Ist Ableitung möglich mit obiger Grammatik?).
NP VP Egon sah Egon

Definition 11.3.7 (Satz einer Grammatik). Eine Zeichenkette aus Terminalsymbolen w ∈ Σ^∗ ist ein Satz einer Grammatik G = ⟨Φ,Σ,R,S⟩, gdw. er aus dem Startsymbol S abgeleitet werden kann:

Definition 11.3.8 (Sprache einer Grammatik G). Die Sprache L_G einer Grammatik G = ⟨Φ,Σ,R,S⟩ ist die Menge aller ihrer Sätze w ∈ Σ^∗.