Mehrdeutige Grammatik

Existieren bzgl. e​iner formalen Grammatik für e​in Wort mehrere Rechtsableitungen o​der Linksableitungen, bzw. g​ibt es z​u einem Wort d​er Grammatik z​wei verschiedene Rechts- o​der zwei verschiedene Linksableitungsbäume, d​ie nicht isomorph zueinander sind, d​ann heißt d​iese Grammatik mehrdeutig.

Beispiel

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.

Siehe auch

• Ableitung (Informatik)
• Inhärent mehrdeutige Sprache