Is every regular language Turing-decidable, and how can we prove this?

Problem Detail: 

I know every regular language is Turing-acceptable, but does that imply it is Turing-decidable?

Asked By : Iancovici

Answered By : Mandar Mitra

Every regular language is Turing-decidable and therefore Turing acceptable / recognisable (but note that Turing acceptable does not imply Turing decidable).

Suppose you are given a DFA D such that L = L(D). One can construct a Turing Machine T that simulates D. T's states will be similar to D's. On reaching the end of the input, if T is in a state that corresponds to a final state of D, T halts and accepts; otherwise it halts and rejects.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10971