Beispiel 5.4

[Bianconeri]

Mein Vorschlag für den Kellerautomaten (ich nenne die Übergangsfunktion hier jetzt F um das einfacher schreiben zu können):

F(q0, 0, B) = {(q1, A, S, R)}
F(q1, 0, B) = {(q0, A, R, R)}
F(q0, 1, B) = {(q0, B, S, L)}
F(q0, 1, A) = {(q2, B, S, L)}
F(q2, 1, A) = {(q2, B, R, L)}
F(q2, Z2, Z0) = {(qf, Z0, S, R)}

[schrankk]

Mein Vorschlag für den Kellerautomaten (ich nenne die Übergangsfunktion hier jetzt F um das einfacher schreiben zu können):

F(q0, 0, B) = {(q1, A, S, R)}
F(q1, 0, B) = {(q0, A, R, R)}
F(q0, 1, B) = {(q0, B, S, L)}
F(q0, 1, A) = {(q2, B, S, L)}
F(q2, 1, A) = {(q2, B, R, L)}
F(q2, Z2, Z0) = {(qf, Z0, S, R)}
hab genauso! :thumb:

[KatzeImSack]

hmmmm....
komischerweise habe ich das genauso - nur ohne den zustand nr. 4
F(q0, 1, A) = {(q2, B, S, L)}


--> das "löschen" eines 1ers macht ihr ja in zeile 3 - oder?
dann müsste es imho gleich mit zeile 5 weitergehen - und jedes A welches geschrieben wurde wird mit jedem 0er der eingelesen wird gelöscht...
(wurde sowieso zuvor doppelt so oft erstellt wie es 0er gibt - somit passts imho wieder)

[Bianconeri]

hmmmm....
komischerweise habe ich das genauso - nur ohne den zustand nr. 4
F(q0, 1, A) = {(q2, B, S, L)}


--> das "löschen" eines 1ers macht ihr ja in zeile 3 - oder?
dann müsste es imho gleich mit zeile 5 weitergehen - und jedes A welches geschrieben wurde wird mit jedem 0er der eingelesen wird gelöscht...
(wurde sowieso zuvor doppelt so oft erstellt wie es 0er gibt - somit passts imho wieder)

Wenn man die 4. Zeile weglässt hat man genau doppelt soviele 1er wie 0er. Man steht ja am Ausgabeband 1 neben den As.

[gonzo69]

schließe mich der lösung an ... normalform wär dann <{q0,q1,q2.qf},{1,0},{z0,A},d,q0,{z0,z1,z2},{qf}>

bin ich da richtig, dass ich beim kellerautomaten, das blanksymbol B nicht in der normalform hab?

[schrankk]

schließe mich der lösung an ... normalform wär dann <{q0,q1,q2.qf},{1,0},{z0,A},d,q0,{z0,z1,z2},{qf}>

bin ich da richtig, dass ich beim kellerautomaten, das blanksymbol B nicht in der normalform hab?
Die Seiten 143 und 149 in Folien beantworten alle deine Frage :thumb:

[krissi]

ist vl eine blöde Frage, aber wieso habt ihr in Zeile 3 und 4 wieder Zustand q0 und keinen neuen? würde da nicht schon q2 sein?
lg

[Clyde]

Habs genau gleich :)

ist vl eine blöde Frage, aber wieso habt ihr in Zeile 3 und 4 wieder Zustand q0 und keinen neuen? würde da nicht schon q2 sein?
lg

Wieso?

Zeile 3: Die erste 1 musst du ja wohl im Zustand q0 lesen, weil du nach jeder gelesenen 0 dich im Zustand q0 befindest. Da liest du auf dem Arbeitsband ein Leersymbol (klar, weil da kann ja nix sein weil wir auf dem Arbeitsband bis jetzt immer nur nach rechts gegangen sind).

Zeile 4: Weil du in Zeile drei beim Lesen der ersten 1 im Zustand q0 geblieben bist, liest du die nächste 1 natürlich wieder im Zustand q0 ein. Da du aber in Zeile 3 auf dem Arbeitsband nach links gegangen bist, liest du dort jetzt aber ein A - deshalb feuert die Übergangsfunktion in Zeile 3 jetzt natürlich nicht, sondern eben diese hier in Zeile 4.