Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » Kontextfreie Sprachen (CFG) » Ableitungsbaum
Kontextfreie Sprachen (CFG) Kontextfreie Sprachen (CFG) Nutzlose Variablen
Unterabschnitte

Ableitungsbaum

Man kann einen Ableitungsbaum für ein Wort einer kontextfreien Sprache erstellen. Anders als bei regulären Sprachen, wo das Wort mit einer Regelfolge erzeugt wird, hat bei einer CFG die Ableitung Baumstruktur.

Rechtsableitung / Linksableitung

Die Rechtsableitung $\Rightarrow_{R}$ bedeutet, daß das am rechtesten stehende Nonterminal zuerst abgeleitet wird.
$\Rightarrow_{R}^{*}$ bedeuted, daß beliebig oft nach rechts abgeleitet wird.
Analog hierzu ist die Linksableitung definiert.

Eindeutigkeit / Mehrdeutigkeit

$G$ heißt eindeutig, wenn es zu jedem Wort $w\in L(G)$ nur genau einen Ableitungsbaum gibt.

$G$ heißt mehrdeutig, wenn es zu einem Wort $w$ mehr als einen Ableitungsbaum gibt.

Eine Grammatik heißt inhärent mehrdeutig, falls es keine Möglichkeit gibt eine eindeutige CFG für die Sprache zu erstellen54.

Fußnoten

... erstellen54
Beispielsweise: $L=\{a^{i}b^{j}c^{k}:i=j\vee j=k\}$

Kontextfreie Sprachen (CFG) Kontextfreie Sprachen (CFG) Nutzlose Variablen