I have been trying to do a product construction(intersection) with 2 DFA which has dead states, but I'm stuck at the transition table with a confusion that,what should I do with dead state. Should I also combine the dead state with other states?


The product construction works for any two DFAs. There is nothing special you need to do. The resulting automaton would have many dead states and so won't be minimal, but that doesn't affect its correctness.

| cite | improve this answer | |
  • $\begingroup$ SO you are saying that if I have 3 states A, B and C(dead state) for one dfa and p, q and r states for the other, then when I combine these states I can have C(Deadstate) p, C(Deadstate) q and C(Deadstate) r ?? $\endgroup$ – DIPIN VARKEY Apr 10 '18 at 16:16
  • $\begingroup$ You can have as many dead states as you wish. The definition of DFA nowhere states that you are only allowed to have at most one dead state. $\endgroup$ – Yuval Filmus Apr 10 '18 at 16:18

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.