Junior Schreiberling
Date of registration: Oct 15th 2002
Location: Berlin
Occupation: IT Application Consultant
Quoted
Original von sr409
So, kurz vor Toresschluss noch eine letzte Aufgabe zu
http://www-thi.informatik.uni-hannover.d…en/uebung08.pdf
Ein LBA der a^n b^n c^n | n>=1 erkennt:
M=({z0,z1,z2,z3,z4,z5}, {a,b,c}, {a,b,c,[],>,<}, o, [], {z5})
o:
;; a suchen und ersetzten
o(z0, a) = o(z1, [], R)
;; b suchen und ersetzen
o(z1, a) = (z1, a, R)
o(z1, []) = (z1, [], R)
o(z1, b) = (z2, [], R)
;; c suchen und ersetzen
o(z2, b) = (z2, b, R)
o(z2, []) = (z2, [], R)
o(z2, c) = (z3, [], L)
;; Zurück zum Anfang
o(z3, a) = (z3, a, L)
o(z3, b) = (z3, b, L)
o(z3, c) = (z3, c, L)
o(z3, []) = (z3, [], L)
o(z3, >) = (z4, >, R)
;; Nächstes a suchen
o(z4, a) = (z1, [], R)
o(z4, []) = (z4, [], R)
o(z4, <) = (z5, <, N)
z5 ist Endzustand
korrekt ?
Habs korrigiert !
Quoted
Original von Cipher
kann man da auch einen 3-Band LBA benutzen ?
(falls es das überhaupt gibt...jedenfalls fällt mir dafür die lösung irgendwie leichter ein )