Notizen

Eindeutige Grammatik

tagstheoretische_informatik, formale_sprachtheorie

Eine Grammatik heißt eindeutig, wenn alle Ableitungen eines Wortes immer zu genau einem Syntaxbaum führen.

Eine nicht eindeutige Grammatik heißt mehrdeutig.

Anmerkungen

  • Mehrdeutigkeit: Eigenschaft Grammatik, nicht notwendigerweise Sprache
  • Mehrdeutige Grammatik: Häufig in eine eindeutige Grammatik mit überführbar
  • Es existieren Sprachen, die ausschließlich durch mehrdeutige Grammatiken erzeugt werdenkönnen (inhärent mehrdeutige Sprachen)

Beispiel

Sprache:

Misplaced &S & \rightarrow aB \ | \ Ac \\ A & \rightarrow ab \\ B & \rightarrow bc \end{align}$$ Wort "abc" bilden: - Möglichkeit 1: $S \Rightarrow Ac \Rightarrow abc$ - Möglichkeit 2: $S \Rightarrow aB \Rightarrow abc$ - $\Longrightarrow$ Sprache is mehrdeutig! **Sprache eindeutig machen:** $$S \rightarrow abc$$

Backlinks