4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How do you show that every regular language is recognizable? Can you use the same technique to show that it's decidable? $\endgroup$ – Shaull Apr 2 '13 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$ – templatetypedef Apr 2 '13 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$ – Raphael Apr 2 '13 at 18:56
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.