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×) 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); } }