Mehrdeutige Grammatik

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Gegeben sei zur Sprache L = \left\{aa\right\} die Grammatik G = \left(\{S, A, B\}, \{a\}, P, S\right) mit L\left(G\right) = L und folgender Regelmenge P:

S \rightarrow AA
S \rightarrow BB
A \rightarrow a
B \rightarrow a

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

S \Rightarrow_G AA \Rightarrow_G aA \Rightarrow_G aa
S \Rightarrow_G BB \Rightarrow_G aB \Rightarrow_G aa

\Rightarrow_G symbolisiert hierbei die Transitionsrelation.

Siehe auch[Bearbeiten]