If the axiom $A_{DFA}$ is known to be decidable, would simply constructing a $DFA$ diagram be enough to prove that $L(M)$ is decidable?

Most of what I can find on the internet tells me that you need to construct a decider (IE, a Turing Machine) in order to prove that a language is decidable. But since it's already established that all languages recognizable by $DFA$'s are decidable, it should be adequate to just show the $DFA$, right?

  • 1
    $\begingroup$ I don't understand your first sentence - what is $A_{DFA}$? What is $M$? The answer to your title question is yes, since DFAs are (essentially) special types of Turing machines, but your first sentence makes me wonder whether this is actually what you are asking. $\endgroup$ – Noah Schweber Dec 11 '15 at 2:03
  • $\begingroup$ I thought it was common notation, sorry. $A_{DFA}$ is the problem of accepting or rejecting a string recognized by a $DFA$. $M$ is just the standard symbol for a generic $DFA$. $\endgroup$ – NmdMystery Dec 11 '15 at 2:04

Yes - if you want to show that a language $L$ is decidable, it is enough to construct a DFA $M$ such that the language accepted by $M$ is precisely $L$ - that is, $L(M)=L$.

The set of pairs $(M, w)$ such that $w$ is a word and $M$ is a DFA which accepts $w$ is decidable. In principal, this is slightly stronger than the decidability of each $L(M)$, since this is a statement about uniform decidability.


You have to be very careful with the sentence

all languages recognizable by DFA's are decidable

For instance, let $L$ be any language of $A^*$. Then the shuffle of $L$ and $A^*$, which is the language $$ L \mathrel{\llcorner\!\llcorner\!\!\!\lrcorner} A^* = \{u_0a_1u_1a_2u_2 \dotsm a_nu_n \mid u_0, u_1, \dots, u_n \in A^*, a_1, \dots, a_n \in A \text{ and }a_1 \dotsm a_n \in L \} $$ is always regular and hence, it is recognized by some finite DFA. However, there is no algorithm to compute this DFA given a non recursively enumerable language $L$.

  • $\begingroup$ Is the statement "all languages recognizable by DFA's are decidable" the same as the acceptance problem? I was either given that statement as an axiom, or something very similar to it. $\endgroup$ – NmdMystery Dec 19 '15 at 20:28
  • $\begingroup$ This is the point: what is the precise meaning of "all languages recognizable by DFA's are decidable"? $\endgroup$ – J.-E. Pin Dec 19 '15 at 20:32
  • $\begingroup$ If a DFA accepts a language, than that language is decidable because regular languages exist solely inside the venn diagram of decidable languages. That's as far as I can really go, because this has to do with an intro class I'm taking. $\endgroup$ – NmdMystery Dec 19 '15 at 21:57
  • $\begingroup$ The question is how you give the language. $\endgroup$ – J.-E. Pin Dec 19 '15 at 23:32
  • $\begingroup$ The language I was given was just one that accepts all even length strings. $\endgroup$ – NmdMystery Dec 19 '15 at 23:37

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.