I know every regular language is Turing-acceptable, but does that imply it is Turing-decidable?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ How do you show that every regular language is recognizable? Can you use the same technique to show that it's decidable? $\endgroup$– ShaullCommented Apr 2, 2013 at 14:10
-
3$\begingroup$ @Raphael- I don't think it's fair to close this question. Many textbooks don't directly address this. I think this question is clearly-written and well-phrased, and the fact that it is not very complicated doesn't seem like a reason to close it. $\endgroup$– templatetypedefCommented Apr 2, 2013 at 17:46
-
1$\begingroup$ @templatetypedef, echadromani: it's not about the level, it's about the SE-badness of the question. The raw information is readily available -- to the point that we have to assume the asker either has the information at hand or the question is homework -- but the asker seems to have some problems with basic definitions. This is not clear, however, from the form of the question. Please see here for a discussion on the matter; if you want to discuss this further, please open a question on Computer Science Meta. $\endgroup$– RaphaelCommented Apr 2, 2013 at 18:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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.
