| Die letzten 4 Beiträge |
| Informatikerin12 |
Lieben Dank für die ausführliche Antwort! 
|
| Karlito |
Hallo Informatikerin12,
die Lösung kann man herleiten, indem man sich Schritt für Schritt vorstellt, was das "Programm" macht. Dazu schaut man sich an, was im Startzustand passiert. Dieser ist hier ![[latex]q_0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?q_0) . In gibt es zwei potentielle Übergänge:
![[latex]<br />
\begin{array}{lll}<br />
\Delta(q_0,a,\sqcup) & = (q_1,a,a,r,0) & \text{ und }<br />
\Delta(q_0,b,\sqcup) & = (q_1,b,b,r,0) &<br />
\end{array}<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
\begin{array}{lll}<br />
\Delta(q_0,a,\sqcup) & = (q_1,a,a,r,0) & \text{ und }<br />
\Delta(q_0,b,\sqcup) & = (q_1,b,b,r,0) &<br />
\end{array}<br />
)
OK, also was sagen uns diese beiden Übergänge. Das erste sagt, dass wen als Erstes vom oberen Band ein a gelesen wird, dieses a wieder auf das Band geschrieben wird. Zusätzlich wird das vom oberen Band gelesene Zeichen auf das untere Band geschrieben. Weiherhin wird der obere Lese-/Schreibkopf nach rechts auf das nächste Zeichen bewegt, der untere bleibt auf der aktuellen Position und es wird in den Zustand ![[latex]q_1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?q_1) gewechselt.
Im Zustand gibt es wiederum zwei Übergänge:
![[latex]<br />
\begin{array}{lll}<br />
\Delta(q_1,x,y) & = (q_1,x,y,r,0) & \text{ und }<br />
\Delta(q_1,\sqcup,y) & = (q_2,\sqcup,y,r,0) &<br />
\end{array}<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
\begin{array}{lll}<br />
\Delta(q_1,x,y) & = (q_1,x,y,r,0) & \text{ und }<br />
\Delta(q_1,\sqcup,y) & = (q_2,\sqcup,y,r,0) &<br />
\end{array}<br />
)
Der erste Übergang sorgt im Prinzip nur dafür, dass das obere Band Zeichen für Zeichen gelesen wird. Dabei wir der obere Lese-/Schreibkopf immer weiter nach rechts bewegt und der Untere bleibt auf der aktuellen Position. Dadurch, dass die Ausgabe immer gleich der Eingabe ist, werden die Bänder nicht verändert. Auch der Zustand ändert sich nicht.
Der zweite Übergang ist eine art Abbruchbedingung. Wird ein Blank-Zeichen [/latex]](http://www.matheboard.de/latex2png/latex2png.php?(\sqcup)) gelesen, so wird der Zustand auf ![[latex]q_2[/latex]](http://www.matheboard.de/latex2png/latex2png.php?q_2) gewechselt und der Kopf wird wieder nach Links zurück auf das letzte Zeichen des oberen Bandes bewegt. Der untere Lese-/Schreibkopf bleibt unverändert.
In Zustand gibt es nur einen Übergang:
![[latex]<br />
\begin{array}{lll}<br />
\Delta(q_2,x,x) & = (q_3,x,x,0,0) &<br />
\end{array}<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
\begin{array}{lll}<br />
\Delta(q_2,x,x) & = (q_3,x,x,0,0) &<br />
\end{array}<br />
)
Nur wenn das Zeichen auf dem oberen Band und das Zeichen auf dem unteren Band übereinstimmen wird in den Zustand ![[latex]q_3[/latex]](http://www.matheboard.de/latex2png/latex2png.php?q_3) gewechselt. Da es ansonsten keine weiteren Übergänge definiert sind, ist das Verhalten der TM nicht definiert. Da die TM sich aber nicht in einem Finalzustand befindet, wird die Eingabe nicht akzeptiert und die Eingabe ist nicht in der Menge der akzeptierten Wörter.
Die Beschreibung ist nicht 100%ig vollständig, da ich nicht auf alle nicht definierten Übergänge, d.h. Randfälle eingegangen bin. Ich hoffe die erschließen sich. Ansonsten und auch wenn es sonst noch Verständnisprobleme gibt gern noch einmal nachfragen.
Es gibt glaube hier keinen Formeleditor. Formeln werden in Form von Latex-Code hier eingebettet. Wenn Du meinen Beitrag zitierst, siehst Du die entsprechenden Quelltexte.
Gruß,
Karlito |
| Informatikerin12 |
Kann mir bitte jemand helfen? Ich zerbreche mir schon seit Tagen den Kopf und kriege es nicht gebacken die Aufgabe zu lösen 
|
| Informatikerin12 |
2-Band-Turingmaschine
Hallo! :-)
In der Aufgabe ist eine 2-Band-Turing-Maschine gegeben und ich muss herausfinden, wie die von M akzeptierte Sprache lautet. Die Lösung hierfür habe ich:
L(M) = {xwx | x Element Sigma, w Element Sigma*} vereinigt mit Sigma.
Wie komme ich auf diese Lösung? Kann mir jemand helfen? Stehe gerade total auf'm Schlauch 
P.S.: Ich finde hier keinen Formeleditor, daher sieht die Lösung nicht optimal aus
Informatikerin12 hat dieses Bild (verkleinerte Version) angehängt:
|
|
|
