Finite State Machines - I
Question 1: Can a Turing Machine be constructed that will perform the same recognition process as a Finite State Machine?
(a) Since a FSM cannot change the contents of an input string (tape) there is no need for any changes in the equivalent Turing Machine.
(b) Starting from the left hand end of the string, transitions in the FSM are equivalent to tape movements and state changes in the Turing Machine.
(c) There is no requirement for a pre-defined ending state in a Turing Machine, though meanings can be given to the halting states. Thus the equivalent ending conditions for a Turing Machine will be:
to have scanned the whole tape and to have ended in a specified state.
Build a machine that recognizes sequences of pairs of alternating 0s and 1s (e.g. 011001 or 100110).
In this example we have identified the preferred ending state for the Turing Machine using the same notation for ending states as used in Finite State Machines. Note that the Turing Machine "transitions" do not change the character on the tape - as required in the FSM. **
Build a machine that recognizes strings that start and finish with 0.
** Problem: How would you modify the machine above to restrict the strings to the SAME pairs of 0s and 1s in every string (e.g. 010101 or 101010)?
CS1104 Main Page
Last Updated 2001/04/20
© J.A.N. Lee, 2000