HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
expressiondfawithregularsinkstatehowdeal

Problem

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?

Solution

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)

Context

StackExchange Computer Science Q#52717, answer score: 2

Revisions (0)

No revisions yet.