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

\begin{slide}{Komprimierte Automatentabellen}

\kopf{$ $Id: tables.tex,v 1.1 2011-10-16 14:06:16 waldmann Exp $ $}

Für det. Aut. braucht man Tabelle (partielle Funktion)
$T:(Q \times \Sigma) \hookrightarrow Q$.
Die ist aber riesengroß, und die meisten Einträge sind leer.
Sie wird deswegen komprimiert gespeichert.
Benutze Felder \verb|next, default, base, check|.

Idee: es gibt viele ähnlichen Zustände:

Zustand $p$ verhält sich wie $q$, außer bei Zeichen $c$: \\
\verb|default[base[p]] = q; check[base[p]+c] = p;|

Übergang $T(p,c)=$ \verb|lookup(p,c)| mit 
\begin{verbatim}
lookup (p, c) {     int a = base[p] + c;
    if  ( p == check[a] ) { return next[a]; }
    else { return lookup (default [p],c); }   }
\end{verbatim}


\end{slide}
