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