Is Dead state is included in the Minimized DFA or not?

finite-automata dfa
Prashant Bhardwaj picture Prashant Bhardwaj · Feb 4, 2012 · Viewed 8.4k times · Source

I searched google and in many pages it is given that in Minimized DFA dead state or trap state is removed. My question is how can it be still a DFA if some transition is undefined. So what you say people?

Answer

Patrick87 picture Patrick87 · Feb 4, 2012

Even minimal DFAs must include dead states; otherwise, they're either (a) not DFAs or (b) not accepting the same language as their non-minimal counterparts. For instance, a minimal DFA for the language {a} over alphabet {a, b} must have 3 states: a start state where you can see a and accept; an accepting state where you reject if you see anything else; and a dead state where you go if you see a b or anything in the accepting state.

Never heard of omitting dead states from minimal DFAs. Blasphemy!

Related questions

Need Regular Expression for Finite Automata: Even number of 1s and Even number of 0s

My problem may sounds different to you. I am a beginner and I am learning Finite Automata. I am googing over Internet to find the Regular Expression for Finite Automata of Given Machine Below. Can anyone help me to write "…

Read More
DFA vs NFA engines: What is the difference in their capabilities and limitations?

I am looking for a non-technical explanation of the difference between DFA vs NFA engines, based on their capabilities and limitations.

Read More
How are finite automata implemented in code?

How does one implement a dfa or an nfa for that matter in Python code? What are some good ways to do it in python? And are they ever used in real world projects?

Read More