imported>M Huhn: Verlinkung

2024-11-08T08:35:09Z

Verlinkung

Neue Seite

Existieren bzgl. einer [[formale Grammatik|formalen Grammatik]] für ein Wort mehrere [[Rechtsableitung]]en oder Linksableitungen, bzw. gibt es zu einem Wort der Grammatik zwei verschiedene Rechts- oder zwei verschiedene Linksableitungsbäume, die nicht [[Isomorphismus|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]].

== Siehe auch ==
* [[Ableitung (Informatik)]]
* [[Inhärent mehrdeutige Sprache]]

[[Kategorie:Compilerbau]]
[[Kategorie:Theorie formaler Sprachen]]

Mehrdeutige Grammatik - Versionsgeschichte

imported>M Huhn: Verlinkung