Turingmaschine umwandeln < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Sei $M=(Q, [mm] \Sigma, \Gamma, \delta, q_0, \#, [/mm] F)$ eine beliebige TM mit [mm] $F=\{f_1, f_2, ..., f_n\}$. [/mm] Erläutern Sie, wie Sie aus M eine äquivalente TM $M'$ entwerfen können, die genau einen akzeptierenden Endzustand enthält. |
Hi Leute!
Kann mir bei dieser Aufgabe jemand einen Denkanstoß geben? Vorab: Ich weiß wie ich mit einer 1-Band TM umgehe und wie ich mit k-Band TM's umgehen muss. Auch habe ich schon gelernt, dass eine TM beliebige TM's simulieren kann. Sowas nennt man dann universelle TM.
Meine erste Frage ist nun folgende: In der Aufgabe steht ja, dass man BESCHREIBEN (nix beweisen also!) soll, wie man nun diese TM mit beliebig vielen akzeptierenden Zuständen zu einer äquivalenten TM mit nur einem akzeptierenden Zustand umbauen kann.
Geht das nun indem man eine universelle TM baut, die die akzeptierenden Zustände [mm] $(f_1, f_2, [/mm] ..., [mm] f_n)$ [/mm] als beliebige Turingmaschinen simuliert?
Ich hab mir das nun mit der BESCHREIBUNG so vorgestellt:
Laut Aufgabendefinition gibt es die Turingmaschinen
TM [mm] $M_1 [/mm] = [mm] (Q_1, \Sigma_1, \Gamma_1, \delta, q_0, \#, F_1)$ [/mm] mit [mm] $Q_1=\{q_0, q_1, ..., q_n\}$ [/mm] und [mm] $F_1=\{f_1\}$,
[/mm]
TM [mm] $M_2 [/mm] = [mm] (Q_2, \Sigma_2, \Gamma_2, \delta, q_0, \#, F_2)$ [/mm] mit [mm] $Q_2=\{q_0, q_2, ..., q_n\}$ [/mm] und [mm] $F_2=\{f_2\}$,
[/mm]
bis
TM [mm] $M_n [/mm] = [mm] (Q_n, \Sigma_n, \Gamma_n, \delta, q_0, \#, F_n)$ [/mm] mit [mm] $Q_n=\{q_0, q_1, ..., q_n\}$ [/mm] und [mm] $F_n=\{f_n\}$.
[/mm]
Die TM $M'$ simuliert nun die TM $M$, in dem sie die TM's [mm] $M_1, M_2, [/mm] ..., [mm] M_n$ [/mm] als geeignete Binärcodierung $<M>$, die Gödelisierung, erhält, und so folgendes gilt,
wenn $M'$ gestartet mit [mm] $ [/mm] x$ sich genauso verhält wie [mm] M_1 [/mm] gestartet mit x, wodurch $M'$ nur einen akzeptierenden Zustand enthält,
wenn $M'$ gestartet mit [mm] $ [/mm] x$ sich genauso verhält wie [mm] M_2 [/mm] gestartet mit x, wodurch $M'$ nur einen akzeptierenden Zustand enthält, und
wenn $M'$ gestartet mit [mm] $ [/mm] x$ sich genauso verhält wie [mm] M_n [/mm] gestartet mit x, wodurch $M'$ nur einen akzeptierenden Zustand enthält.
Könnte man diese Beschreibung so machen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:11 Fr 14.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
