Turingmaschine entwerfen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:10 Di 28.05.2013 | | Autor: | bandchef |
| Aufgabe | Entwerfen Sie eine TM $M=(Q, [mm] \Sigma, \Gamma, \delta, q_0, \#, [/mm] F)$, die der folgenden Spezifikation entspricht:
- Eingabe: [mm] $x_1 x_2 [/mm] ... [mm] x_n \text{ mit } x_i \in \{a,b\}$
[/mm]
- Ausgabe: [mm] $x_1 x_1 x_2 x_2 [/mm] ... [mm] x_n x_n \text{ mit } x_i \in \{a,b\}$ [/mm] |
Hi Leute!
Ich soll obige TM entwerfen. Ich hab hier aber schon bei der Überlegung und am Papier durchspielen Probleme, wie das gehen soll. Ich hab mir schon überlegt, ein weiteres Zeichen bspw. ein $ einzuführen, dass mir sagt wo die letzte Hinzufügung geschehen ist. Vorher muss natürlich das gesamte Wort in einen Teil des unendlichen Bandes kopiert werden, damit ich weiß welche Zeichen die nächsten sind. Aber irgendwie klappt das alles nicht!
Kann mir jemand helfen?
|
|
| |
|
Hallo bandchef,
>
> Ich soll obige TM entwerfen. Ich hab hier aber schon bei
> der Überlegung und am Papier durchspielen Probleme, wie
> das gehen soll. Ich hab mir schon überlegt, ein weiteres
> Zeichen bspw. ein $ einzuführen, dass mir sagt wo die
> letzte Hinzufügung geschehen ist. Vorher muss natürlich
Schon mal gut, Du musst wissen, wo Du zuletzt hinzugefügt hast. Aber brauchst Du dafür wirklich noch ein weiteres Zeichen (was Du sicher lt. Definition Eurer TM gar nicht einführen dürfest)? Du hast doch schon das Blank! Damit geht das.
> das gesamte Wort in einen Teil des unendlichen Bandes
> kopiert werden, damit ich weiß welche Zeichen die
> nächsten sind. Aber irgendwie klappt das alles nicht!
Du musst nicht das gesamte Wort neu kopieren. Probiere es doch mal andersrum. Schreib doch das neue Wort auf leeres Band. Hilft das schon als Tipp?
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:58 Mi 29.05.2013 | | Autor: | bandchef |
> Schreib doch das neue Wort auf leeres Band.
Hm ok, leuchtet ein. Aber dann brauch ich doch auch noch ein drittes Zeichen (ich weiß, das wäre zuwider der vorgebenen TM-Definition!), dass mir markiert, wo das neue verdoppelte Wort anfängt, oder? Denn ansonsten kopier ich das linkeste Zeichen des vorgegebenen Wortes neben das rechteste Zeichen des vorgegebenen Wortes und keiner weiß mehr, wo das neue verdoppelte Wort beginnt, oder sehe ich den Trick doch noch nicht?
|
|
|
| |
|
Hallo bandchef,
> > Schreib doch das neue Wort auf leeres Band.
>
> Hm ok, leuchtet ein. Aber dann brauch ich doch auch noch
> ein drittes Zeichen (ich weiß, das wäre zuwider der
> vorgebenen TM-Definition!), dass mir markiert, wo das neue
> verdoppelte Wort anfängt, oder? Denn ansonsten kopier ich
> das linkeste Zeichen des vorgegebenen Wortes neben das
> rechteste Zeichen des vorgegebenen Wortes und keiner weiß
> mehr, wo das neue verdoppelte Wort beginnt, oder sehe ich
> den Trick doch noch nicht?
Naja, was spricht denn dagegen, dass Du zwischen altem und neuen Wort ein Blank lässt?  Blanks sind hier sowieso DAS Stichwort..oder nenn es Trick ;) *in die richtige Richtung schubs*
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:09 Mi 29.05.2013 | | Autor: | bandchef |
Ich hab mir dann hier mal Gedanken zu meiner DTM gemacht. Ich hab hier heute nur ein Bild keinen LaTeX-Code weil mir diese große Liste zu aufwendig geworden wäre. Ich denke man kann aber dennoch alles gut erkennen!
DTM: http://s7.directupload.net/file/d/3270/b6xjpf3e_jpg.htm
Richtig?
|
|
|
| |
|
Hallo bandchef,
> Richtig?
Die Idee ist richtig. Allerdings noch nicht korrekt umgesetzt.
Ein paar Denkanstöße:
Welcher Zustand soll denn Dein F sein? Kommt Deine DTM je in so einen Zustand?
Und wird aus einer Eingabe von beispielsweise #aba# wirklich ein #aabbaa# oder eher ein aa?
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:49 Do 30.05.2013 | | Autor: | bandchef |
Hier nochmal meine DTM: http://s7.directupload.net/file/d/3271/5tl9luj7_jpg.htm
Ich denke jetzt erstellt sie Wörter der Form aabbaa für aba. Auch einen Finalzustand q9 hab ich eingeführt, einen Fehler in Zustand [q8 (q8,b,L) anstatt (q7,b,L)] und fehlende Übergänge in q3 und q4 hinzugefügt.
Kannst du mir sagen ob das jetzt so passt?
|
|
|
| |
|
Hallo bandchef,
> Hier nochmal meine DTM:
> http://s7.directupload.net/file/d/3271/5tl9luj7_jpg.htm
>
> Ich denke jetzt erstellt sie Wörter der Form aabbaa für
> aba. Auch einen Finalzustand q9 hab ich eingeführt, einen
> Fehler in Zustand [q8 (q8,b,L) anstatt (q7,b,L)] und
> fehlende Übergänge in q3 und q4 hinzugefügt.
>
> Kannst du mir sagen ob das jetzt so passt?
Noch nicht ganz. Denn eigentlich ist es ja so, dass in einem Endzustand die Kopfposition, das Band und der Zustand nicht mehr verändert wird. D.h. es darf in einem Endzustand keine Veränderungen mehr geben... Das solltest Du vielleicht dahingehend noch mal überdenken.
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:39 Do 30.05.2013 | | Autor: | bandchef |
So, jetzt nochmal: Jetzt hab ich hoffentlich einen richtigen finalen Zustand (q10) eingebaut: http://s14.directupload.net/file/d/3271/4esckfut_jpg.htm
|
|
|
| |
|
Hallo bandchef,
> So, jetzt nochmal: Jetzt hab ich hoffentlich einen
> richtigen finalen Zustand (q10) eingebaut:
> http://s14.directupload.net/file/d/3271/4esckfut_jpg.htm
Der finale Zustand ist jetzt richtig. Aber wie sieht es denn jetzt z.B. mit dem Eingabewort #aaba# aus, wird das korrekt verdoppelt?
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:22 Fr 31.05.2013 | | Autor: | bandchef |
Im Zustand q9 beim Lesen eines # stand bisher nichts. Es muss aber (q0,#,R) stehen. Jetzt sollte das passen.
Hier nochmal das Bild: http://s14.directupload.net/file/d/3272/krgsx86l_jpg.htm
Ich hoffe endlich dass das jetzt stimmt!
|
|
|
| |
|
Hallo bandchef,
> Im Zustand q9 beim Lesen eines # stand bisher nichts. Es
> muss aber (q0,#,R) stehen. Jetzt sollte das passen.
>
> Hier nochmal das Bild:
> http://s14.directupload.net/file/d/3272/krgsx86l_jpg.htm
>
> Ich hoffe endlich dass das jetzt stimmt!
Wird denn jetzt #aaba# korrekt verdoppelt?
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:32 Fr 31.05.2013 | | Autor: | bandchef |
Meiner Ansicht nach wird nun aaba korrekt zu aaaabbaa verdoppelt!
|
|
|
| |
|
Hallo bandchef,
> Meiner Ansicht nach wird nun aaba korrekt zu aaaabbaa
> verdoppelt!
Wie soll das gehen, wenn ich mir [mm] q_8 [/mm] anschaue?
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:23 Sa 01.06.2013 | | Autor: | bandchef |
Ich habe nun heute mit dieser TM http://s14.directupload.net/file/d/3272/krgsx86l_jpg.htm (die gleiche wie gestern!) nochmal aaba durchgespielt und die ewigen Zustände aufgeschrieben. Ich komme auf ein korrekt verdoppeltes Wort.
Kannst du mir deine Zweifel genauer erläutern?
|
|
|
| |
|
Hallo bandchef,
> Ich habe nun heute mit dieser TM
> http://s14.directupload.net/file/d/3272/krgsx86l_jpg.htm
> (die gleiche wie gestern!) nochmal aaba durchgespielt und
> die ewigen Zustände aufgeschrieben. Ich komme auf ein
> korrekt verdoppeltes Wort.
>
> Kannst du mir deine Zweifel genauer erläutern?
Also...man hat #aaba#. Dann geht es los:
q0 zu q1 ##aba#
durch mehrmaliges q1 zu q3 ##aba##
q3 zu q5 ##aba#a#
q5 zu q7 ##aba#aa#
richtig? Und nun würden mich mal Deine - sagen wir mal nächsten 5 Schritte - interessieren. Wie geht es weiter?
Gruß
Anna
|
|
|
|
