Informatik 3

Äquivalenzreaktionen

Hier können wir das akzeptierveralten bestimmen bzw. formal ausdrücken
Das machen wir wenn wir einzelnd sachen definieren, und diese modifizieren. Wenn dabei nicht dasselbe rauskommt, sind die dinger die wir uns anschauen nicht equivaelent
ein DFA ist minimal, wenn alle Strings die äquivalent sind zu demselben Zustand führen
Wenn die nerode Relation einer sprache $L$ endlichen index hat, dann kann ein DFA für $L$ konstruiert werden
- Dieser DFA verwendet dann die vorher definierten Äquivalenzklassen
- Deswegen nennen wir das ding dann auch äquivalenzklassenautomaten

Die dinger nutzen wir um herauszufinden, ob zwei dinge Äquivalent sind
Folie 12
Wie gesagt, wir dein wort genau dann vom Automaten akzeptiert, wenn wir das wort mit einem wohl definierten "modifikator" modifiziert wird und das erwartete Ergebnis dabei dann heraus kommt

Kein DFA für eine reguläre Sprache ist kleiner als ihr Äquivalenzklassenautomat
Wir könen aber auch Verfeinerungen betrachten
- Die haben dann mindestens so viele Äquivalenzklassen wie die Relation die sie verfeinert
- Genau so trifft natürlich auch mindestens alles aus der zu verfeinernen Relation zu

Eine Sprache $L$ ist genau dann regulär, wenn $r_{L}$ endlich viele äquivalenzklassen hat
- Hieraus können wir die Methode zum Nachweis basteln, und ebenfalls eine Methode um nachzuweisen, dass das am ende nicht regulär ist