Kontextfreie Grammatik

Definition

Eine Grammatik ist kontextfrei falls alle Regeln die Form $A⟶w$ haben mit $A\in N,w\in (\Sigma \cup N{)}^{\ast }$

Satz

Jede Kontextfreie Grammatik lässt sich umformen in eine äquivalente Grammatik in Chomsky-Normalform .

Leerheitsproblem für kontextfreie Grammatiken

Vereinfachung kontextfreier Grammatiken

Terminirend

Erreichbar

Zusammen

siehe auch:

• Chomsky-Normalform
• Pumping Lemma