Seite 1 von 1

2DFA gleichmächtig zu DFA Beweis - Blatt 8

BeitragVerfasst: 16 Mär 2014, 19:24
von Fabian
Bei der Bearbeitung von Übungsblatt 8 sind wir über die 8.5 gestoplert. Die im Vorhinein gegbene Tabellendefinition T_x sollen hier angewendet werden. Aus den Vorlesungsnotizen geht hervor, dass die Tabellendefinition dazu dient die Gleichmächtigkeit zwischen 2DFA und DFA zu beweisen. Allerdings können wir diesen Gedankenschritt nicht ganz nachvollziehen. Wir würden uns über ein paar erklärende Worte freuen, inwieweit die resultierenden Tabellen zeigen, dass die Myhill-Nerode Relation des zwei DFAs einen endlichen Index hat.

Re: 2DFA gleichmächtig zu DFA Beweis - Blatt 8

BeitragVerfasst: 18 Mär 2014, 13:17
von tobias.blass
Hi,
die Tabelle drückt das kurz gesagt deshalb aus weil die Tabelle nur endlich viele Einträge hat und es nicht mehr Äquivalenzklassen als Einträge geben kann.

Die Begründung dafür ist wie folgt:
Man wählt sich x beliebig. Jetzt sind alle Wörter y in derselben Äquivalenzklasse wie x für die gilt:
\forall z: xz \in L <=> yz \in L

Wenn es jetzt mehr Äquivalenzklassen als Einträge in der Tabelle T_x gibt, dann gibt es einen Eintrag in der Tabelle der zu zwei Äquivalenzklasse gehört. Dieser Eintrag spezifiziert aber den gesamten Zustand des 2DFA für die Position direkt hinter x, d.h. der Automat müsste vom selben Zustand aus unterschiedliche Wege gehen um tatsächlich 2 Äquivalenzklassen darzustellen. Das kann offensichtlich nicht sein.

Ich hoffe das macht es klarer (und entschuldigung wenn das nicht exakt die Vorgehensweise der VL ist, ich habe den Kozen momentan nicht vor mir)
Gruß
Tobias

Re: 2DFA gleichmächtig zu DFA Beweis - Blatt 8

BeitragVerfasst: 18 Mär 2014, 21:57
von Fabian
Jup, das macht es klarer.
Dankeschön ;)