1
$\begingroup$

As turing machine always halts on dead configuration,so consider the case where it halts in final state,if on second last state by reading an input alphabet it comes to final state. Now in final state it will try to find the transition for the next symbol(i.e blank) and as there will be no transition on final state so machine will halt/dead in final and we can say string is accepted.

If i consider the case of Finite automate,now FA reaches the final state and the next is blank then we say machine will stop and string is accepted.But this is not dead configuration.

But in both cases the input is coming from tape and in case of FA ,it will halt when blank comes on tape and there is no dead configuration.But same behaviour in TM is having dead configuration behaviour.

Can someone please explain the difference in these two case from point of dead configuration.?

P.S:- By dead configuration,i mean that transition on the state is not defined for given alphabet

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

Turing machines (and RAM machines) and (most) finite automata operate in two different input models. Finite automata usually accept their input in a streaming fashion: they read one input symbol, do something, read another input symbol, do something, and so on. When the input is exhausted, they report their output. Turing machines, in contrast, get all their input on the input tape, and then do whatever processing they wish. They don't have to stop after they have scanned the entire input.

This difference in the input model explains the different semantics you have indicated. There are, however, finite automata which have input semantics similar to a Turing machine, namely two-way finite automata. Although behaving superficially like Turing machines, they are equivalent in power to deterministic finite automata (DFAs).

Improve this answer
$\endgroup$
2
  • $\begingroup$ As you mentioned "Finite automata usually accept their input in a streaming fashion". Can you elaborate on this statement?I was under impression that FA also reads input from tape. $\endgroup$
    – rahul sharma
    Commented Sep 12, 2017 at 14:59
  • $\begingroup$ DFAs and NFAs read the input symbols one by one. You can imagine that the inputs are written on a tape which is read cell by cell, but you can also imagine that at each step someone whispers to the automaton the next input symbol. This is known as the streaming model. $\endgroup$
    – Yuval Filmus
    Commented Sep 12, 2017 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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