1
$\begingroup$

The title should explain my question thoroughly enough. I can't seem to get started anywhere. Intuitively it seems like some kind of brute-forcing would work i.e if the DFA has the symbols $\Sigma$ you would simply be passing strings from $\Sigma^*$ until the DFA rejects. What would even be the time complexity of this though? Or am I completely out and about?

$\endgroup$
1
$\begingroup$

The problem with your approach is that there are infinitely many strings in $\Sigma^*$. If the automaton keeps accepting and accepting, how would you know hen to stop?

Instead, consider how an automaton can reject: it rejects by getting to a rejecting state.

$\endgroup$
  • $\begingroup$ So basically seeing if it is possible to not reach an accept state? $\endgroup$ – user3380251 Nov 15 '18 at 19:43
  • $\begingroup$ @user3380251 Not quite. If it's possible to not reach an accept state, there's at least one string that's rejected. You want it to be not possible to reach an accepting state, so all inputs are rejected. $\endgroup$ – David Richerby Nov 15 '18 at 19:55
  • $\begingroup$ Oh I think my title may have been confusing. I changed it from "any" to "some". My DFA is not rejecting all strings, but rather some string. $\endgroup$ – user3380251 Nov 15 '18 at 19:57
  • $\begingroup$ @user3380251 Then your reasoning is correct. I've edited my answer to reflect the changed question. $\endgroup$ – David Richerby Nov 15 '18 at 20:16
  • 1
    $\begingroup$ Thank you! Then I'll get back to work. Always good with some good input (that is an intentional pun) $\endgroup$ – user3380251 Nov 15 '18 at 20:22

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.