Kontextfreie Sprachen

Id: cf.tex,v 1.1 2011-10-11 18:13:54 waldmann Exp

Def (Wdhlg): G ist kontextfrei (Typ-2), falls ∀(l, r)∈R(G) : lV.

geeignet zur Beschreibung von Sprachen mit hierarchischer Struktur.

Anweisung -> Bezeichner = Ausdruck
    | if Ausdruck then Anweisung else Anweisung
Ausdruck -> Bezeichner | Literal
    | Ausdruck Operator Ausdruck

Bsp: korrekt geklammerte Ausdrücke: G = ({a, b},{S}, S,{SaSbS, Sε}).

Bsp: Palindrome: G = ({a, b},{S}, S,{SaSa, SbSb, Sε).

Bsp: alle Wörter w über Σ = {a, b} mit | w|a = | w|b



Johannes Waldmann 2013-01-28