CODEWITHSUNDEEP
automatacomputation-theorydfa
C_beginner
C_beginner

Reputation: 295

How to partition the states of a DFA having a dead state during minimisation of the same

When we want to minimise a DFA,at first we partition the final and non-final states.Then we divide those states into several more partitions until all the states in each partition belong to the same equivalence class.Now my question is suppose we have a dead state in the dfa then should it go to the partition of non-final states or to a separate partition(containg only the dead state)?Also please tell me whether that dead state should be counted as one of the states in the minimised dfa?

Upvotes: 2

Views: 1409

Answers (1)

templatetypedef
templatetypedef

Reputation: 372784

The dead state goes into the set of non-final states, because it's not an accepting state.

You treat dead states just like any other (non-final) state during the minimization algorithm. When you're done, if your DFA needs a dead state at all, it should have a dead state as one of its states. If other states in the DFA have no paths to any accepting state, they're effectively dead and will be merged with the dead state during minimization.

Some regular languages require dead states, but the algorithms are "smart" enough to ensure that they're included.

Hope this helps!

Upvotes: 4

Related Questions