Reduzierte Automaten
Id: reduz.tex,v 1.1 2003/11/10 13:52:47 joe Exp
Ein Zustand eines Automaten heißt
heißt reduziert, wenn alle Zustände nützlich sind.
Satz: Zu jedem Automaten gibt es einen reduzierten Automaten mit .
Beweis: erst auf erreichbare Zustände einschränken, ergibt , dann auf produktive Zustände einschränken, ergibt .
Deteministische Automaten
Id: det.tex,v 1.3 2003/11/10 13:52:47 joe Exp
heißt vollständig, wenn es zu jedem wenigstens ein mit gibt.
heißt deterministisch, falls
Satz: Zu jedem Automaten gibt es einen deterministischen und vollständigen Automaten mit .
Potenzmengen-Konstruktion
Id: potenz.tex,v 1.1 2003/11/10 13:52:47 joe Exp
Idee: betrachten Mengen von erreichbaren Zuständen
mit
Minimierung von det. Aut. (I)
Id: min.tex,v 1.1 2003/11/10 13:52:47 joe Exp
Idee: Zustände zusammenlegen, die ,,das gleiche`` tun. Das ,,gleich`` muß man aber passend definieren: benutzen Folgen von Äquivalenz-Relationen auf .
Zustände und verhalten sich für alle Eingaben der Länge beobachtbar gleich: .
äquivalent ist induktive Definition:
Minimierung von det. Aut. (II)
Nach Definition ist jeder Relation eine Verfeinerung der Vorgänger: . Da die Trägermenge endlich ist, kann man nur endlich oft verfeinern, und es gibt ein mit . Wir setzen .
Konstruiere mit
Satz: Wenn vollständig und deterministisch,
dann ist ein kleinster vollst. det. Aut mit
.
Endliche Automaten als Scanner
Id: scan.tex,v 1.2 2003/11/10 13:52:47 joe Exp
Während ein Automat nur akzeptiert (oder ablehnt), soll ein Scanner die Eingabe in Tokens zerteilen.
Gegeben ist zu jedem Tokentyp ein Ausdruck , der genau die Token-Werte zu beschreibt.
Der Eingabestring soll so in Wörter zerlegt werden, daß
Automaten als Scanner (II)
Man konstruiert aus den Automaten und vereinigt diese, markierte jedoch vorher ihre Endzustände (jeweils mit ). Dann deterministisch und minimal machen.
Beim Lesen der Eingabe zwei Zeiger mitführen: auf Beginn des aktuellen matches, und letzten durchlaufenen akzeptierenden Zustand.
Falls Rechnung nicht fortsetzbar, dann bisher besten match ausgeben, Zeiger entsprechend anpassen, und wiederholen.
Beachte: evtl. muß man ziemlich weit vorausschauen:
Tokens , Eingabe .
Komprimierte Automatentabellen
Id: tables.tex,v 1.2 2003/11/10 13:52:47 joe Exp
Für det. Aut. braucht man Tabelle (partielle Funktion)
.
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 verhält sich wie , außer bei Zeichen :
default[base[p]] = q; check[base[p]+c] = p;
Übergang 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); } }
Scanner mit Flex (I)
Id: flex.tex,v 1.2 2003/11/10 13:52:47 joe Exp
Das Programm flex
erzeugt aus einer Scanner-Beschreibung
einen Scanner (ein C-Programm).
Wie beschrieben wird aus regulären Ausdrücken ein (markierter) deterministischer Automaten bestimmt.
Beim Feststellen eines matches kann eine Aktion ausgeführt werden (default: String ausgeben).
Bei mehreren gleichlangen matches wird der (im Quelltext) erste genommen.
Damit der Scanner niemals hängt, gibt es einen Default-Tokentyp, der (zuletzt) jedes einzelne Zeichen matcht (und ausgibt).
Scanner mit Flex (II)
DIGIT [0-9] %% DIGIT+ { fprintf (stdout, "%s", yytext); } " "+ { fprintf (stdout, " "); } "\n" { fprintf (stdout, "\n"); } %% int yywrap () { return 1; } int main ( int argc, char ** argv ) { yylex (); }Aufruf mit
flex -t simple.l > simple.c
. Optionen:
-T
(Table) zeigt Automatentabellen
-d
(debug),
-f
(fast) ohne Tabellen-Kompression