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

${\displaystyle S\rightarrow AA}${\displaystyle S\rightarrow AA}

${\displaystyle S\rightarrow BB}${\displaystyle S\rightarrow BB}

${\displaystyle A\rightarrow a}${\displaystyle A\rightarrow a}

${\displaystyle B\rightarrow a}${\displaystyle B\rightarrow a}

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

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

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

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

• Ableitung (Informatik)
• Inhärent mehrdeutige Sprache

• Compilerbau
• Theorie formaler Sprachen