5
$\begingroup$

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:

  1. 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.
  2. 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.

  3. 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.

  4. 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.

  5. Thus trap state is always a dead state.
  6. 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?
  7. As I write these points and think, now, I feel both concepts are one and the same and I am unnecessarily getting confused.
  8. 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?

$\endgroup$

1 Answer 1

4
$\begingroup$

The concepts you mention are not formal concepts. You can define several notions of a dead state, for example (focusing on DFAs):

  1. A dead state is a non-accepting state with self-loops for all symbols.
  2. As in definition 1, but we also require the state to be reachable.
  3. A dead state is a state from which no accepting state is reachable.
  4. As in definition 3, but we also require the state to be reachable.

If we allow some transitions to be "missing" (i.e., our definition of DFA defines the transitions function as a partial function rather than as a function) then we have more possibilities, for example:

  1. A dead state is a non-accepting state in which all outgoing transitions are self-loops.
  2. As in definition 1, but we also require the state to be reachable.
  3. A dead state is a non-accepting state without outgoing transitions.
  4. As in definition 3, but we also require the state to be reachable.

If the exact definition used matters, the concept should be explicitly defined. It is usually used in a somewhat informal way, in which the intended meaning is usually obvious from context.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.