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.

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

${\displaystyle S\rightarrow AA}$

${\displaystyle S\rightarrow BB}$

${\displaystyle A\rightarrow a}$

${\displaystyle B\rightarrow a}$

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

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

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

${\displaystyle \Rightarrow _{G}}$ symbolisiert hierbei die Transitionsrelation.

• Ableitung (Informatik)
• Inhärent mehrdeutige Sprache