| Die letzten 5 Beiträge |
| 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 
|
| NixJava |
So, mein dritter Beitrag. 
Es müsste gelten: NTM = DTM = 2-PDA > PDA > DEA = NEA = epsilon-NEA |
| NixJava |
| 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. |
| NixJava |
| 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. |
| 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:
| 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 |
|
|
