I need some help to prove that the language is decidable.

$K$ = {$N$ : $N$ is a DFA (Sigma = {a, b, c}) and $L$($N$) contains at least one word in which there is no a}.

It tried to make an algorithm which receives as input a DFA $N$ and which determines whether or not this automaton accepts at least one word which contains no a. But it's kinda complex so any help would be appreciated.


A DFA is essentially a directed multi-graph $G$ in which a distinguished vertex is marked as the initial state $s$, a set $T$ of vertices are marked as accepting states, and edges are labelled with the symbols of $\Sigma$.

The problem is then equivalent to that of deciding whether there is a path on $G$ that goes from $s$ to a vertex in $T$, and uses only edges that are not labelled with $a$.

It suffices to delete all the edges labelled with $a$ from $G$ and to run any graph visit algorithm from $s$. If a vertex in $T$ is discovered you can immediately accept. If the visit terminates and no vertex in $T$ is discovered, then reject.


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.