Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Nutzlose Variablen Aufwärts: Kontextfreie Sprachen (CFG) Vorherige Seite: Kontextfreie Sprachen (CFG)   Inhalt

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\}$