Kontextfreie Sprachen

Id: cf.tex,v 1.2 2005/11/02 23:37:52 waldmann Exp

Def (Wdhlg): G ist kontextfrei (Typ-2), falls $ \forall$(l, r) $ \in$ R(G) : l $ \in$ V.

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,{S$ \to$aSbS, S$ \to$$ \epsilon$}).

Bsp: Palindrome: G = ({a, b},{S}, S,{S$ \to$aSa, S$ \to$bSb, S$ \to$$ \epsilon$).

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



Johannes Waldmann 2006-02-02