Kontextfreie Sprache

Einfache Sprache

Def. Kontextfreie Sprache

Eine Sprache wird Kontextfreie Sprache, wenn sie die Produzierte Sprache einer kontextfreien Grammatik ist.

Alternative: Eine Sprache $L$ ist eine Kontextfreie Sprache, falls eine Kontextfreie Grammatik $\mathcal G =(T,V,S.P)$ so existiert, dass

$$L = \left\{w\in T^*\mid S\overset{*}{\underset{\mathcal G}\Rightarrow} w\right\}\;.$$

Es muss also für jedes Wort in $L$ eine erweiterte Ableitung von $S$ nach $w$ geben.