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=\left(\{S,A,B\},\{a\},P,S\right)$ mit $L\left(G\right)=L$ und folgender Regelmenge $P$:

$S\rightarrow AA$

$S\rightarrow BB$

$A\rightarrow a$

$B\rightarrow 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