Refer to the following TM. We assume that the input string is put on the T_APE with the symbol # inserted in front of it in cell i. For example, the input ha will be run with the T_APE initially in the form #ba∇ . . . . In this chapter, we saw how to do this using TM states. Here, consider it already done. The TM is then

Trace the execution chains of the following i nput strings on this machine:
(i) aa
(ii) aaa
(iii) aaaa
(iv) aabaab
(v) abab

Transcribed Image Text:

START (#,#,R) (A,A,R) (B.B.R) (a.a,L) (b,b,L) (Y,*.L) 11 (*.*.L) (B.B.L) (A.A.L) (a.A.R) (b.B.R) (b.b.L) (a.a.L) (A,A,L) (B.B.L) (*.*.R) (A.A.R) (B.B.R) (B,#,R) (#,#,R) 7 (*.*,R) 8 (A,A,R) 13 (#,#,R) (a,a, R) (b,b,R) HALT (b,Y,L) (a,X,L) (A,A,L) (B.B.L) (A,#,R) (#,#,R) (..R) 4 (A,A,L) (X,X,L) (Y.Y.L) (a.a.R)| (b,b,R) (B,B,R) (*.*.R) (A,A,R) 10 (X,*.L) 12 (B,B,L) (*.*.L) (A.A.L)