 Äquivalenz von Turingmaschinen und Automaten |
InformaTiger 
Tripel-As
Dabei seit: 19.02.2013
Beiträge: 228
Herkunft: Südtirol
 |
|
| Ä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
__________________
Why do Java developers wear glasses? Because they can't C#
|
|
29.02.2020 13:24 |
|
|
NixJava
unregistriert
|
|
| 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.
|
|
|
29.02.2020 14:49 |
|
|
NixJava
unregistriert
|
|
| 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.
|
|
|
29.02.2020 15:10 |
|
|
NixJava
unregistriert
|
|
So, mein dritter Beitrag.
Es müsste gelten: NTM = DTM = 2-PDA > PDA > DEA = NEA = epsilon-NEA
|
|
|
29.02.2020 15:18 |
|
|
InformaTiger
Tripel-As
Dabei seit: 19.02.2013
Beiträge: 228
Herkunft: Südtirol
|
|
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 
__________________
Why do Java developers wear glasses? Because they can't C#
|
|
|
29.02.2020 15:18 |
|
|
|
