1
$\begingroup$

Is $L = \{\langle A\rangle\mid A\text{ is a DFA and }L(A) = \Sigma^*\}$ decidable?

I know that $L'=\{\langle A,w\rangle \mid A\text{ is a DFA and }w\in L(A)\}$ is decidable, but I'm not sure if this is related.

$\endgroup$
3
$\begingroup$

It's decidable. Think about what an DFA's accepting states must look like if it accepts every possible string. That property is very easy to check.

$\endgroup$
1
$\begingroup$

Yes.

Every accessible state $s$

  • must be accepted
  • must have a successor state $\tau (s, \sigma)$ for $\sigma \in \Sigma$, where $\tau$ is the transition function of the DFA.

You can check this by breadth-first (or depth-first or whatever) search from the initial state. The search terminates since the automaton is finite.

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