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 (Unmittelbare Ableitungsrelation). Die unmittelbare Ableitungsrelation ⇒ ⊆ Γ^∗ × Γ^∗ einer Grammatik ist die Menge aller Paare ⟨u,v⟩ mit u,v,w,z ∈ Γ^∗, für die gilt:

• es gibt eine Regel der Form w → z
• die Zeichenketten u und v können so in Teilzeichenketten aufgeteilt werden, dass gilt: u = u₁ ∙ w ∙ u₂ sowie v = u₁ ∙ z ∙ u₂

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 unmittelbar oder mittelbar voneinander abgeleitet werden können.

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

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