tm.cpp starting // l0n1na.tm with trace all // accept the language L = { 0^n 1^n | n>0 } // book page 150 Fig. 7.2 reading input finished. start state q0 states:q0 q1 q2 q3 q4 final states:q4 trace states:q0 q1 q2 q3 q4 Sorted transition table: q0 0 q1 X R q0 Y q3 Y R q1 0 q1 0 R q1 1 q2 Y L q1 Y q1 Y R q2 0 q2 0 L q2 X q0 X R q2 Y q2 Y L q3 #b q4 #b R q3 Y q3 Y R q4 #b q4 #b N tape = 01 step 1 q0 0 at pos 1 tape=01 ^ transition to state=q1 write=X move=R step 2 q1 1 at pos 2 tape=X1 ^ transition to state=q2 write=Y move=L step 3 q2 X at pos 1 tape=XY ^ transition to state=q0 write=X move=R step 4 q0 Y at pos 2 tape=XY ^ transition to state=q3 write=Y move=R step 5 q3 at pos 3 tape=XY ^ transition to state=q4 write= move=R step 6 q4 #] at pos 4 tape=XY ^ tape accepted after 6 steps, at q4 tape = 0011 step 1 q0 0 at pos 1 tape=0011 ^ transition to state=q1 write=X move=R step 2 q1 0 at pos 2 tape=X011 ^ transition to state=q1 write=0 move=R step 3 q1 1 at pos 3 tape=X011 ^ transition to state=q2 write=Y move=L step 4 q2 0 at pos 2 tape=X0Y1 ^ transition to state=q2 write=0 move=L step 5 q2 X at pos 1 tape=X0Y1 ^ transition to state=q0 write=X move=R step 6 q0 0 at pos 2 tape=X0Y1 ^ transition to state=q1 write=X move=R step 7 q1 Y at pos 3 tape=XXY1 ^ transition to state=q1 write=Y move=R step 8 q1 1 at pos 4 tape=XXY1 ^ transition to state=q2 write=Y move=L step 9 q2 Y at pos 3 tape=XXYY ^ transition to state=q2 write=Y move=L step 10 q2 X at pos 2 tape=XXYY ^ transition to state=q0 write=X move=R step 11 q0 Y at pos 3 tape=XXYY ^ transition to state=q3 write=Y move=R step 12 q3 Y at pos 4 tape=XXYY ^ transition to state=q3 write=Y move=R step 13 q3 at pos 5 tape=XXYY ^ transition to state=q4 write= move=R step 14 q4 #] at pos 6 tape=XXYY ^ tape accepted after 14 steps, at q4 tape = 011 step 1 q0 0 at pos 1 tape=011 ^ transition to state=q1 write=X move=R step 2 q1 1 at pos 2 tape=X11 ^ transition to state=q2 write=Y move=L step 3 q2 X at pos 1 tape=XY1 ^ transition to state=q0 write=X move=R step 4 q0 Y at pos 2 tape=XY1 ^ transition to state=q3 write=Y move=R step 5 q3 1 at pos 3 tape=XY1 ^ No next transition, quitting now tape rejected after 5 steps, at q3 No more input tapes. Stopping.