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 <math>L = \left\{aa\right\}</math> die Grammatik <math>G = \left(\{S, A, B\}, \{a\}, P, S\right)</math> mit <math>L\left(G\right) = L</math> und folgender Regelmenge <math>P</math>:
- <math>S \rightarrow AA</math>
- <math>S \rightarrow BB</math>
- <math>A \rightarrow a</math>
- <math>B \rightarrow a</math>
Die Grammatik <math>G</math> ist mehrdeutig, weil zur Erzeugung des Wortes <math>aa</math> zwei verschiedene Linksableitungen angegeben werden können.
- <math>S \Rightarrow_G AA \Rightarrow_G aA \Rightarrow_G aa</math>
- <math>S \Rightarrow_G BB \Rightarrow_G aB \Rightarrow_G aa</math>
<math>\Rightarrow_G</math> symbolisiert hierbei die Transitionsrelation.