Kontextfreie Sprachen

mathend000#Id mathend000#

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

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→aSbS, S→ε}) mathend000#.

Bsp: Palindrome: G = ({a, b},{S}, S,{S→aSa, S→bSb, S→ε) mathend000#.

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