# DFA to regular expression how to deal with 'sink state'

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?

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

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