Karl Pech
2005-03-29 10:41:21 UTC
Hallo allerseits,
Ich habe da zu folgender Aufgabe eine etwas größere DTM gebastelt und wollte
eigentlich nur wissen, ob sie so richtig ist. (Wenn nicht, so wäre es schön,
wenn mir da jemand ein Wort angeben könnte, die diese TM nicht akzeptieren sollte,
aber es trotzdem tut; Oder aber ein Wort, welches die TM akzeptieren sollte.
Vielleicht wäre ein Korrekturhinweis dann auch nicht schlecht.)
Ok, die Aufgabe lautete:
###
Geben Sie eine TM für die Sprache L := {w \in {0, 1}^+ | w enthält die gleiche Anzahl
von Nullen und Einsen} an.
###
Meine Idee:
´´´´´´´´´´´
Die TM sortiert das vorgegebene Wort mit BubbleSort (die nicht optimierte Variante,
weil diese am einfachsten ist). Anschließend begrenzt die TM das Wort rechts durch
ein 'E'. Das Wort ist jetzt zwischen '\blank' und 'E' eingeschlossen und ist in
der Form 0^n 1^m . Die TM sucht die "Mitte" des Wortes (Übergang von 1 zu 0:
0.._01_...1 ). Ausgehend von der Wortmitte ersetzt die TM im "Zick-Zack"-Verfahren,
0'en und 1'en durch 'X'. Ist das Wort anschließend in der Form \blank (X)^+ E, so
war das vorherige Wort in der Form 0^n 1^n ansonsten nicht. Durch das Zick-Zack-Verfahren
kommt die TM nämlich entweder zum \blank (linke Grenze) oder zum E (rechte Grenze).
Dort angekommen läuft sie nach rechts (nach links) und liest alle X. Sie bricht ab, wenn
sie auf ein nicht-X trifft, weil kein Übergang dazu existiert. Erreicht die TM aber
die rechte (linke) Grenze, so war das Wort tatsächlich von der Form 0^n 1^n und \in L.
Umsetzung der Idee:
´´´´´´´´´´´´´´´´´´´
M = ({q_0,...,q_15}, {0, 1}, {0, 1, T, t, E, X, \blank}, d, q_0, \blank, {q_15})
/* BubbleSort */
d(q_0, 0) = (q_0, 0, R) // "00, 01"-Blöcke ==> nicht tauschen
d(q_0, 1) = (q_1, 1, R) // "1?"-Block ==> Tausch möglich
d(q_1, 1) = (q_1, 1, R) // "11"-Block ==> nicht tauschen; weiter
d(q_1, 0) = (q_2, 1, L) // "10"-Block ==> "1_0_" --> "_1_1" ==> ...
d(q_2, 1) = (q_3, T, R) // ... ==> "T_1_" Merke dir die Stelle, wo du warst.
/* Wir benutzen ein Feld außerhalb des Wortes als Boolesche Variable, die gesetzt wird,
wenn min. 1x getauscht wurde. */
d(q_3, 0) = (q_3, 0, R); d(q_3, 1) = (q_3, 1, R); // Wort verlassen ...
d(q_3, \blank) = (q_4, \blank, R); d(q_4, \blank) = (q_5, t, L) // Variable auf 'wahr' setzen ...
// ... und wieder ins Wort zum T zurückkehren.
d(q_5, \blank) = (q_5, \blank, L); d(q_5, 0) = (q_5, 0, L); d(q_5, 1) = (q_5, 1, L);
d(q_5, T) = (q_0, 0, R); // damit ist der Tausch beendet: "10" --> Variable setzen --> "0_1_"
// Wortende erreicht ==> gehe zur Variable
d(q_0, \blank) = (q_6, \blank, R);
d(q_1, \blank) = (q_6, \blank, R);
// while(b_wurde_getauscht) {...}
d(q_6, t) = (q_7, \blank, L);
d(q_6, \blank) = (q_9, \blank, L)
// Es wurde min. 1x getauscht
d(q_7, \blank) = (q_8, \blank, L);
d(q_8, 0) = d(q_8, 0, L); d(q_8, 1) = d(q_8, 1, L);
d(q_8, \blank) = d(q_0, \blank, R); /* Wir gehen also wieder an den Anfang des Wortes zurück
und sortieren nocheinmal. */
// Es wurde nicht mehr getauscht ==> Wort ist in Form 0^n 1^m sortiert
d(q_9, \blank) = (q_10, E, L); // Begrenze das Wort (\blank (0)^+ (1)^+ E)
d(q_10, 1) = (q_10, 1, L); // Gehe über alle (1)^+ zur Wortmitte
d(q_10, 0) = (q_11, X, R); // Zick-Zack-Verfahren initialisiert
// Lauf über alle X nach rechts und ersetze die rechte angrenzende 1 ...
d(q_11, X) = (q_11, X, R); d(q_11, 1) = (q_12, X, L);
// ... Lauf dann wieder zurück nach links und ersetze dort die linkeste benachbarte 0;
// u.s.w.
d(q_12, X) = (q_12, X, L); d(q_12, 0) = (q_11, X, R);
// Irgendwann stossen wir entweder auf die rechte oder linke Grenze
d(q_11, E) = (q_13, \blank, L);
d(q_12, \blank) = (q_14, \blank, R);
// Jetzt durchlaufen wir nochmal das Wort (X)^+ bzw. (X)^+ E und prüfen, ob auch wirklich
// überall X steht.
d(q_13, X) = (q_13, \blank, L);
d(q_13, \blank) = (q_15, \blank, N); // Wort \in L
d(q_14, X) = (q_14, \blank, R);
d(q_14, E) = (q_15, \blank, N); // Wort \in L
So, das war's. Wer schön, wenn das jemand noch irgendwie kommentieren würde. Sicherlich gibt
es da noch eine einfachere Lösung für die obige Sprache, oder?
Grüße
Karl
--
[Werbung] "Greift nach den Sternen auf www.vorhilfe.de !" =))) [/Werbung]
Ich habe da zu folgender Aufgabe eine etwas größere DTM gebastelt und wollte
eigentlich nur wissen, ob sie so richtig ist. (Wenn nicht, so wäre es schön,
wenn mir da jemand ein Wort angeben könnte, die diese TM nicht akzeptieren sollte,
aber es trotzdem tut; Oder aber ein Wort, welches die TM akzeptieren sollte.
Vielleicht wäre ein Korrekturhinweis dann auch nicht schlecht.)
Ok, die Aufgabe lautete:
###
Geben Sie eine TM für die Sprache L := {w \in {0, 1}^+ | w enthält die gleiche Anzahl
von Nullen und Einsen} an.
###
Meine Idee:
´´´´´´´´´´´
Die TM sortiert das vorgegebene Wort mit BubbleSort (die nicht optimierte Variante,
weil diese am einfachsten ist). Anschließend begrenzt die TM das Wort rechts durch
ein 'E'. Das Wort ist jetzt zwischen '\blank' und 'E' eingeschlossen und ist in
der Form 0^n 1^m . Die TM sucht die "Mitte" des Wortes (Übergang von 1 zu 0:
0.._01_...1 ). Ausgehend von der Wortmitte ersetzt die TM im "Zick-Zack"-Verfahren,
0'en und 1'en durch 'X'. Ist das Wort anschließend in der Form \blank (X)^+ E, so
war das vorherige Wort in der Form 0^n 1^n ansonsten nicht. Durch das Zick-Zack-Verfahren
kommt die TM nämlich entweder zum \blank (linke Grenze) oder zum E (rechte Grenze).
Dort angekommen läuft sie nach rechts (nach links) und liest alle X. Sie bricht ab, wenn
sie auf ein nicht-X trifft, weil kein Übergang dazu existiert. Erreicht die TM aber
die rechte (linke) Grenze, so war das Wort tatsächlich von der Form 0^n 1^n und \in L.
Umsetzung der Idee:
´´´´´´´´´´´´´´´´´´´
M = ({q_0,...,q_15}, {0, 1}, {0, 1, T, t, E, X, \blank}, d, q_0, \blank, {q_15})
/* BubbleSort */
d(q_0, 0) = (q_0, 0, R) // "00, 01"-Blöcke ==> nicht tauschen
d(q_0, 1) = (q_1, 1, R) // "1?"-Block ==> Tausch möglich
d(q_1, 1) = (q_1, 1, R) // "11"-Block ==> nicht tauschen; weiter
d(q_1, 0) = (q_2, 1, L) // "10"-Block ==> "1_0_" --> "_1_1" ==> ...
d(q_2, 1) = (q_3, T, R) // ... ==> "T_1_" Merke dir die Stelle, wo du warst.
/* Wir benutzen ein Feld außerhalb des Wortes als Boolesche Variable, die gesetzt wird,
wenn min. 1x getauscht wurde. */
d(q_3, 0) = (q_3, 0, R); d(q_3, 1) = (q_3, 1, R); // Wort verlassen ...
d(q_3, \blank) = (q_4, \blank, R); d(q_4, \blank) = (q_5, t, L) // Variable auf 'wahr' setzen ...
// ... und wieder ins Wort zum T zurückkehren.
d(q_5, \blank) = (q_5, \blank, L); d(q_5, 0) = (q_5, 0, L); d(q_5, 1) = (q_5, 1, L);
d(q_5, T) = (q_0, 0, R); // damit ist der Tausch beendet: "10" --> Variable setzen --> "0_1_"
// Wortende erreicht ==> gehe zur Variable
d(q_0, \blank) = (q_6, \blank, R);
d(q_1, \blank) = (q_6, \blank, R);
// while(b_wurde_getauscht) {...}
d(q_6, t) = (q_7, \blank, L);
d(q_6, \blank) = (q_9, \blank, L)
// Es wurde min. 1x getauscht
d(q_7, \blank) = (q_8, \blank, L);
d(q_8, 0) = d(q_8, 0, L); d(q_8, 1) = d(q_8, 1, L);
d(q_8, \blank) = d(q_0, \blank, R); /* Wir gehen also wieder an den Anfang des Wortes zurück
und sortieren nocheinmal. */
// Es wurde nicht mehr getauscht ==> Wort ist in Form 0^n 1^m sortiert
d(q_9, \blank) = (q_10, E, L); // Begrenze das Wort (\blank (0)^+ (1)^+ E)
d(q_10, 1) = (q_10, 1, L); // Gehe über alle (1)^+ zur Wortmitte
d(q_10, 0) = (q_11, X, R); // Zick-Zack-Verfahren initialisiert
// Lauf über alle X nach rechts und ersetze die rechte angrenzende 1 ...
d(q_11, X) = (q_11, X, R); d(q_11, 1) = (q_12, X, L);
// ... Lauf dann wieder zurück nach links und ersetze dort die linkeste benachbarte 0;
// u.s.w.
d(q_12, X) = (q_12, X, L); d(q_12, 0) = (q_11, X, R);
// Irgendwann stossen wir entweder auf die rechte oder linke Grenze
d(q_11, E) = (q_13, \blank, L);
d(q_12, \blank) = (q_14, \blank, R);
// Jetzt durchlaufen wir nochmal das Wort (X)^+ bzw. (X)^+ E und prüfen, ob auch wirklich
// überall X steht.
d(q_13, X) = (q_13, \blank, L);
d(q_13, \blank) = (q_15, \blank, N); // Wort \in L
d(q_14, X) = (q_14, \blank, R);
d(q_14, E) = (q_15, \blank, N); // Wort \in L
So, das war's. Wer schön, wenn das jemand noch irgendwie kommentieren würde. Sicherlich gibt
es da noch eine einfachere Lösung für die obige Sprache, oder?
Grüße
Karl
--
[Werbung] "Greift nach den Sternen auf www.vorhilfe.de !" =))) [/Werbung]