André Vratislavsky

Übungsgruppe vom 16.11.99

Erzeugen eines regulären Ausdrucks durch dynamische Programmierung.

Wir wollten beweisen, daß die  regulären Sprachen den dfa-Sprachen entsprechen.
Dazu haben wir gezeigt, daß jede reguläre Sprache auch dfa-Sprache ist (Satz 1.9 der Vorlesung), d.h für jede reguläre Sprache gibt es einen endlichen Automaten, der sie erkennt.
Nun bleibt noch die andere Richtung zu zeigen: Jede dfa-Sprache ist regulär (Satz 1.15 der Vorlesung), d. h. jeder endliche Automat M erkennt eine reguläre Sprache.
Gegeben sei also ein endlicher Automat M. Dann ist ein regulärer Ausdruck zu konstruieren, der die von M erkannte Sprache darstellt.

Die Beweisidee:

Erzeugen eines regulären Ausdrucks durch dynamische Programmierung.
Dazu werden die in der Vorlesung definierten Teilsprachen L_r,i,t verwendet:
L_r,i,t sind alle Teilworte, die entstehen, wenn man vom Zustand q_r zum Zustand q_t in der Maschine läuft, wobei man auf dem Weg von q_r nach q_t nur
Zwischenzustände aus {q₁,q₂,...,q_i} benutzen darf. Diese können auch mehrfach verwendet werden. q_r und q_t zählen nicht zu den Zwischenzuständen (es sei
denn, r=i oder t=i).
L_r,0,t sind alle Teilworte, die entstehen, wenn man vom Zustand q_r zum Zustand q_t in der Maschine läuft, wobei man auf dem von q_r nach q_t keinen Zwischenzustand benutzen darf.
L_r,0,t ist nach Definition regulär.
L_s,n,f = L(M) wird durch folgende Rekursionsformel aufgebaut:
L_r,i+1,t = L_r,i,t v L_r,i,i+1 . (L_i+1,i,i+1)* . L_i+1,i,t

Für L_r,i+1,t werden nur Operationen verwendet, die reguläre Ausdrücke erzeugen. Also ist L_s,n,f = L(M) für n Zustände, Startzustand s und Endzustand f regulär.

Zustandsminimierung bei endlichen Automaten

Gegeben ein dfa A. Gesucht ist der zu A äquivalente Äquivalensklassenautomat, der minimale Zustandszahl hat.

Zwei Zustände heißen äquivalent <=> ( für alle Wörter w gilt: delta(p,w) aus F gdw delta(q,w) aus F )

Idee: Alle äquivalenten Zustände zusammenfassen, denn von dort aus gelangt man zu demselben Ergebnis (akzeptiert bzw. nicht akzeptiert).

Algorithmus zur Minimierung eines dfa

1. Tabelle aller Zustandspaare {q_i, q_j}, i#j aufstellen.
2. Markieren aller Paare {q_i, q_j}, für die gilt: (q_i aus F und q_j nicht aus F) oder umgekehrt. Diese sind nicht äquivalent, denn mit dem leeren Wort als Zeuge gelangt man zu einem akzeptierenden und einem nicht akzeptierenden Zustand.
3. Für jedes unmarkierte Paar {q_i, q_j} teste für alle a aus Sigma, ob {delta(q_i,a),delta(q_j,a)} in Tabelle markiert. Wenn ja, markiere {q_i,q_j}. Denn es gibt ein Wort, mit dem man rekursiv zu einem akzeptierenden und zu einem nicht akzeptierenden Zustand gelangt.
4. Wiederhole 3. solange, bis keine Änderung mehr in der Tabelle vorgenommen wurde.
5. Alle nicht markierten Paare sind teilweise untereinander äquivalent.