2DFA gleichmächtig zu DFA Beweis - Blatt 8

Hier könnt ihr euch über die Inhalte der Übungsblätter austauschen und Fragen stellen.

2DFA gleichmächtig zu DFA Beweis - Blatt 8

Beitragvon Fabian » 16 Mär 2014, 19:24

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.
Fabian
 
Beiträge: 2
Registriert: 16 Okt 2013, 18:17

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

Beitragvon tobias.blass » 18 Mär 2014, 13:17

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
tobias.blass
 
Beiträge: 3
Registriert: 17 Okt 2013, 00:38

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

Beitragvon Fabian » 18 Mär 2014, 21:57

Jup, das macht es klarer.
Dankeschön ;)
Fabian
 
Beiträge: 2
Registriert: 16 Okt 2013, 18:17


Zurück zu Übungsblätter

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron