State Read Write Move New State A 0 D R A A 1 O R A A L B

State

Read

Write

Move

New State

A

0

D

R

A

A

1

O

R

A

A

#

!

L

B

B

D

E

L

B

B

O

N

N

Halt

Walk through the machine for the input tape shown below ( starting in state A with the inital head position at the first number 0. When the machine halts, whta does the tape read?

0 1 1 0 #

|

Solution

Assuming that the position is left by 1 unit

Initial state = A

so when we encounter an 0, the machine will write D and move R will stay at stage A

so when we encounter 1, the machine will write 0 and move L will stay at stage A, output DO

so when we encounter 1, the machine will write 0 and move R will stay at stage A, output DOO

so when we encounter an 0, the machine will write D and move R will stay at stage A, output DOOD

so when we encounter an #, the machine will write ! and move R will stay at stage B, output DOOD!

With the given sequence the machine will not halt since in order to be halt the machine should get a 0 in stage B mode, but with the last symbol # machine enters in the B stage mode hence it will never enter halt condition

Final output wil be DOOD! and machine will stop taking input, if we continue this loop, it will print NDOOD! and wil become halted