Äquivalenz von Turingmaschinen und Automaten |
29.02.2020, 13:24 | Auf diesen Beitrag antworten » | ||
InformaTiger | Äquivalenz von Turingmaschinen und Automaten Hallo liebe Community, ich bin gerade bei der Klausurvorbereitung "Diskrete Mathematik" und habe dort eine Multiple-Choice Aufgabe die folgendermaßen lautet:
Laut Antwortenschlüssel müsste E richtig sein. Jedoch ist meiner Meinung nach D richtig. Laut unserem Skriptum besteht eine Äquivalenz zwischen DTM und NTM. Desweiteren sind Turingmaschinen und 2-Kellerautomaten äquivalent. Ein Kellerautomat ist ein endlicher Automat. Da Automaten, also DEA, NEA und epsilon-NEA untereinander äquivalent sind, sollte aus jeder Turingmaschine ein äquivalenter epsilon-NEA gebaut werden können. Die Recherche im Internet bestätigt diese Vermutung. Liege ich damit richtig oder habe ich irgendwo einen Denkfehler? Mit freundlichen Grüßen, InformaTiger |
||
|
|||
29.02.2020, 14:49 | Auf diesen Beitrag antworten » | ||
NixJava |
Das kann nicht sein, weil eine TM deutlich mächtiger als ein DEA ist. Ich denke, der Fehler liegt darin, dass ein 2-PDA nicht äquivalent zu einem PDA ist. |
||
29.02.2020, 15:10 | Auf diesen Beitrag antworten » | ||
NixJava |
Das stimmt auch nicht. Ein DEA erkennt nur die regulären Sprachen, ein PDA sogar die kontextfreien Sprachen. Daher wird die Diskrepanz zwischen TM und DEA noch größer. |
||
29.02.2020, 15:18 | Auf diesen Beitrag antworten » | ||
NixJava | So, mein dritter Beitrag. Es müsste gelten: NTM = DTM = 2-PDA > PDA > DEA = NEA = epsilon-NEA |
||
Anzeige | |||
|
|||
29.02.2020, 15:18 | Auf diesen Beitrag antworten » | ||
InformaTiger | NixJava, ok das macht natürlich Sinn. Nach unserer Definition ist ein 2-Kellerautomat allerdings ein endlicher Automat, mit noch zusätzlich 2 Kellern (Stapel). Ich war warscheinlich deshalb etwas verwirrt. Ist jetzt klar, danke |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |