Mehrdeutige Grammatik

Existieren bzgl. einer formalen Grammatik für ein Wort mehrere Rechtsableitungen oder Linksableitungen, bzw. gibt es zu einem Wort der Grammatik zwei verschiedene Rechts- oder zwei verschiedene Linksableitungsbäume, die nicht isomorph zueinander sind, dann heißt diese Grammatik mehrdeutig.

Beispiel

Gegeben sei zur Sprache $L=\left\{aa\right\}$ die Grammatik $G=(\{S,A,B\},\{a\},P,S)$ mit $L\left(G\right)=L$ und folgender Regelmenge $P$:

$S\to AA$

$S\to BB$

$A\to a$

$B\to a$

Die Grammatik $G$ ist mehrdeutig, weil zur Erzeugung des Wortes $aa$ zwei verschiedene Linksableitungen angegeben werden können.

$S{\Rightarrow }_{G}AA{\Rightarrow }_{G}aA{\Rightarrow }_{G}aa$

$S{\Rightarrow }_{G}BB{\Rightarrow }_{G}aB{\Rightarrow }_{G}aa$

${\Rightarrow }_G$ symbolisiert hierbei die Transitionsrelation.

Siehe auch

• Ableitung (Informatik)
• Inhärent mehrdeutige Sprache