Komprimierte Automatentabellen

Id: tables.tex,v 1.1 2007-10-31 17:50:50 waldmann Exp

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

Idee: es gibt viele ähnlichen Zustände:

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

Übergang T(p, c) = lookup(p,c) mit

lookup (p, c) {     int a = base[p] + c;
    if  ( p == check[a] ) { return next[a]; }
    else { return lookup (default [p],c); }   }