Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
 |
|
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
|
|
