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 $\mathcal 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