Is constructing a DFA enough to prove that a language is decidable?

Question

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?

Answer 1

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.

Answer 2

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$.