snippetMinor
Is every regular language Turing-decidable, and how can we prove this?
Viewed 0 times
thiscanregulareveryandlanguagedecidableprovehowturing
Problem
I know every regular language is Turing-acceptable, but does that imply it is Turing-decidable?
Solution
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.
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.
Context
StackExchange Computer Science Q#10971, answer score: 7
Revisions (0)
No revisions yet.