%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Kontextfreie Sprachen}

\kopf{$ $Id: cf.tex,v 1.1 2011-10-16 14:06:17 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.

\begin{verbatim}
Anweisung -> Bezeichner = Ausdruck
    | if Ausdruck then Anweisung else Anweisung
Ausdruck -> Bezeichner | Literal
    | Ausdruck Operator Ausdruck
\end{verbatim}

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$ 

\dots und ähnlich Aufgaben, siehe demnächst autotool.

\end{slide}
