Well, this sounds somewhat basic definitions, but I feel they needs to be clearly defined.
In book by Hopcroft et. al., there is an excerpt:
...a dead state, that is, a nonaccepting state that goes to itself on every possible input symbol...
In book by Peter Linz, there is an excerpt:
...the automaton finds itself in state $q_2$, with the transition $\delta(q_2,0)$ undefined. We call such a situation a dead configuration...
The same book have following excerpt too:
... the dfa goes into state $q_2$, from which it can never escape. The state $q_2$ is a trap state.
So I want to know if following facts are correct:
- Trap state is one from which we cannot escape, that is, it has either no transitions defined or transitions for all symbols goes to itself.
I feel, definition on this page for dead state is more correct:
Once the machine enters a dead state, there is no way for it to reach an accepting state.
So a trap state can be final or non final, since both can have either no transitions defined or have transitions for every symbol happening to itself.
Earlier I felt:
A final state cannot be a dead state, as we can read $\epsilon$ and stay in the same state, which is final state.
But this, seems incorrect, as epsilon moves are not allowed in DFAs.
- Thus trap state is always a dead state.
- It does not makes sense to have non-trap dead state. I mean it makes no sense to show outgoing transition from dead state, if that transition does not lead to some final state further on its path. Thus dead state is always a trap state. Right?
- As I write these points and think, now, I feel both concepts are one and the same and I am unnecessarily getting confused.
This page also has following statement:
Techincally, this automaton is not a DFA, because it lacks transitions on most symbols from each of its states.
then it says:
...add a transition to the dead state from each other state $q$, on all input symbols for which $q$ has no other transition. The result will be a DFA in the strict sense.
I feel DFA (regardless of any attribute attached to it: strict or non strict) can have dead state as it does not eliminates its "deterministic" nature. Right?