If you were given a state transition diagram could you tell, just by looking at the diagram, if the diagram represented a DTM or a DFA (especially if it was unlabeled, just a directed graph)? Would there be any difference between the diagram representing the deterministic Turing machine and the diagram representing the deterministic finite automata, or is the difference between them in the context that surrounds the diagram and in the labeling ie. one can read and write to the tape while the other can only read?


Summary : you may still be able to tell them apart , but not necessarily

First refere to the formal definition to a Turing machine from Wikipedia

Now consider the transition function δ :

  1. First , δ does not allow transitions from accepting states , so in a state diagram of a TM you expect some state to have no transitions from it , unlike a DFA where every state must have transitions out of it , other definitions of TMs allow transitions from final states , but have accept/reject states taking effect immediately , and so you don't expect these states to have transitions

  2. δ is a partial function , thus you don't need to define a transition for each state and each symbol , unlike DFAs which require a transition from each on each symbol (refer to Wikipedia under complete and incomplete) , so in a DFA you have all states having equal number of transitions/arrows from them but not necessarily in a Turing machine

Arguments :

  1. 1 would be nullified if TM and DFA have no final states to begin with
  2. 2 can also be nullified should we choose to provide transition from all states on all symbols for a TM , or go for the less common alternative definition for the DFA in Wikipedia and then not all states need to have equal number of transitions

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.