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

\begin{slide}{Ableitungsbäume für CF-Sprachen}

\kopf{$ $Id: baum.tex,v 1.1 2006-10-16 19:50:57 waldmann Exp $ $}

Def: ein geordneter Baum $T$ 
mit Markierung $m: T \to \Sigma\cup\{\epsilon\}\cup V$
ist Ableitungsbaum für eine CF-Grammatik $G$, wenn:
\begin{itemize} \itemsep 0pt
\item für jeden inneren Knoten $k$ von $T$ gilt $m(k) \in V$
\item für jedes Blatt $b$ von $T$ gilt $m(b) \in\Sigma \cup \{\epsilon\}$
\item für die Wurzel $w$ von $T$ gilt $m(w)=S(G)$ (Startsymbol)
\item für jeden inneren Knoten $k$ von $T$ 
  mit Kindern  $k_1, k_2, \ldots, k_n$ gilt 
  $(m(k), m(k_1) m(k_2) \ldots m(k_n)) \in R(G)$
  (d. h. jedes $m(k_i) \in V \cup\Sigma$)
\item für jeden inneren Knoten $k$ von $T$
  mit einzigem Kind $k_1 = \epsilon$ gilt
  $(m(k), \epsilon)\in R(G)$.
\end{itemize}


\end{slide}

\begin{slide}{Ableitungsbäume (II)}

Def: der \emph{Rand} eines geordneten, markierten Baumes $(T,m)$
ist die Folge aller Blatt-Markierungen (von links nach rechts).

Beachte: die Blatt-Markierungen sind $\in \{\epsilon\} \cup \Sigma $,
d. h. Terminalwörter der Länge 0 oder 1.

\newcommand{\rand}{\operatorname{rand}}

Für Blätter: $\rand(b)=m(b)$, 
für innere Knoten: $\rand(k)=\rand(k_1) \rand(k_2)\ldots \rand(k_n)$

Satz: $w \in L(G) \iff$ existiert Ableitungsbaum $(T,m)$ für $G$
mit $\rand(T,m)=w$.

\end{slide}
