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.

BeispielBearbeiten

Gegeben sei zur Sprache   die Grammatik   mit   und folgender Regelmenge  :

 
 
 
 

Die Grammatik   ist mehrdeutig, weil zur Erzeugung des Wortes   zwei verschiedene Linksableitungen angegeben werden können.

 
 

  symbolisiert hierbei die Transitionsrelation.

Siehe auchBearbeiten