Mehrdeutige Kontextfreie Grammatik

Einfache Sprache

Def. Mehrdeutige Kontextfreie Grammatik

Eine Kontextfreie Grammatik $\mathcal G = (T,V,S,P)$ ist mehrdeutig, wenn ein Wort $w\in T^*$ so existiert, dass wir zwei unterschiedliche komplette Syntaxbäume mit yield $w$ in $\mathcal G$ finden können.

Beispiel

Sei $\mathcal G$ eine KFG mit $\mathcal G = (\{1,2\}, \{S\},S,P)$ wobei $P$ die Produktionsregel $S\to S+S\;|\; S*S\;|\;2\;|\;1$. Dann sind zwei mögliche Ableitungen

$$E\Rightarrow E+E\Rightarrow E+E*E\overset{*}\Rightarrow1+2*2$$

und

$$E\Rightarrow E*E\Rightarrow E+E*E\overset{*}\Rightarrow 1+2*2\;.$$

Als Syntaxbäume jeweils und

Bemerke: Obwohl das Wort am Ende gleich ist, sehen die Syntaxbäume anders aus. Wenn wir nun $+$ und $*$ wie gewohnt interpretieren ergibt sich $1+2*2=1+4=5$ und $1+2*2=3*2=6$.

$\mathcal G$ ist also mehrdeutig, da für ein Wort $w:=1+2*2$ mehrere Syntaxbäume existieren.