Mehrdeutige Grammatik

Gegeben sei eine formale Grammatik

N stehe hierbei wie üblich für die Menge der Nichtterminalsymbole, Σ für die Menge der Terminalsymbole, P für eine Menge von Regeln und S für das Startsymbol (vgl. formale Grammatik).

Die Grammatik heißt mehrdeutige Grammatik, wenn sie für ein Wort w ∈ L(G) verschiedene Linksableitungen ermöglicht.

Beispiel

Gegeben sei zur Sprache L = {aa} die Grammatik

mit L(G) = L und

Zur Erzeugung des Wortes aa lassen sich jetzt zwei Linksableitungen angeben, nämlich

und

symbolisiert hierbei die Transitionsrelation.

Siehe auch: Ableitung (Informatik), Inhärent mehrdeutige Sprache