1
$\begingroup$

I can’t understand How can dfa have more than one sink state? Isn’t it the same state? Maybe there is some examples

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Consider the following automaton.

enter image description here

There are two sink states: $q_3$ and $q_4$. Of course, any automaton with multiple sink states is equivalent to an automaton with at most one sink state, and even to an automaton without any sink state if the automaton is not complete.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Even for complete automata we can artificially remove sink states by splitting them into a pair of non-accepting states pointing to one-another. We get a sink connected component, a kind of trap. $\endgroup$
    – Hendrik Jan
    Jan 19 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.