Mehrdeutige Grammatik
# 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.

