Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Berechenbarkeits- und Komplexitätstheorie (http://www.informatikerboard.de/board/board.php?boardid=15)
----- Äquivalenz von Turingmaschinen und Automaten (http://www.informatikerboard.de/board/thread.php?threadid=4284)
Geschrieben von InformaTiger am 29.02.2020 um 13:24:
Ä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:
| Zitat: |
Welche der folgenden Aussagen zu Turingmaschinen und regulären Sprachen ist richtig?
- Die Teilmengenkonstruktion wandelt eine nichtdeterministische Turingmaschine in eine deterministische um
- Bei einer 3-Band Turingmaschine, die einen DEA simuliert, bewegen sich die Leseköpfe immer in unterschiedliche Richtungen.
- Die Klasse der Sprachen, die von einer Mehrband-Turingmaschine akzeptiert werden, ist echt größer als die Klasse der Sprachen, die von einer 1-Band-Turingmaschine akzeptiert werden.
- Jede Turingmaschine kann in einen äquivalenten epsilon-NEA umgewandelt werden.
- Keine der Aussagen.
|
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
Geschrieben von NixJava am 29.02.2020 um 14:49:
| Zitat: |
| sollte aus jeder Turingmaschine ein äquivalenter epsilon-NEA gebaut werden können. |
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.
Geschrieben von NixJava am 29.02.2020 um 15:10:
| Zitat: |
| Ein Kellerautomat ist ein endlicher Automat. |
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.
Geschrieben von NixJava am 29.02.2020 um 15:18:
So, mein dritter Beitrag.
Es müsste gelten: NTM = DTM = 2-PDA > PDA > DEA = NEA = epsilon-NEA
Geschrieben von InformaTiger am 29.02.2020 um 15:18:
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
Forensoftware: Burning Board, entwickelt von WoltLab GmbH