3
$\begingroup$

Didn't find a clear statement on this so I just want to make sure I'm right. If I have DFA with edges leading to a 'sink state' (non-accepting state we don't get out of) the edges leading to the sink state and the edge from the sink to itself won't get any representation in the regular expression right? We can just remove those edges and stated at the beginning.. Am I right?

$\endgroup$
  • $\begingroup$ Did you check our reference question to see how the different algorithms deal with this? $\endgroup$ – Raphael Feb 5 '16 at 13:13
2
$\begingroup$

Yes, if you have a DFA with a state $q_{rej}$ acting as a sink state, then it is there only for the formal definition of the DFA, so that our DFA will "know" to reject any other inputs that loop in there. An NFA on the other hand, does have to have a sink state, and you can just erase it. A DFA must describe what to do on each input, whether it is an input that will be accepted or whether rejected. An NFA describes which words you will accept, it has no need to describe which you reject. A regular expression works on the same principal, it only describes which inputs you accept, it does not describe which are rejected.

Hope this clarified your question.

(note that you cannot remove those edges and the sink state in the DFA, because, as stated above, a DFA must decide an answer on each input, even if it loops in a sink state. Removing it will result in an NFA)

$\endgroup$
1
$\begingroup$

It depends on the definition you take for a DFA. If you insist that your DFA should be complete, that is, if the transition function is a total function from $Q \times A$ to $Q$, then you need to keep the sink state. But if you consider an incomplete DFA (that is, the transition function is only a partial function from $Q \times A$ to $Q$), then you can remove the sink state.

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