#MADE EASY

Question

Is this statement right or wrong?

A DFA does not contain a dead configuration.

and what is the mean of dead configuration exactly?

Answer 1

NFA doesn’t have dead configuration or we can say there is no need for dead configuration in NFA as in NFA we only try to give transitions for alphabets (input symbols) which are part of valid strings, for invalid strings in NFA there is no transitions available.

For DFA we have to give transition for every input alphabet at every state. like an example of DFA for exactly two b’s, so in this DFA there will a dead state which will trap all the strings having greater than two b’s.

Comments

Actually there is nothing as such dead configuration it’s just a normal state in DFA same like other states only difference is it has a transition to all input alphabates to itself (loop back transition for every possible input alphabet) and if this state is not final state, think if some string while processing reach this state which has every transition to itself will this string ever be accepted, it will never make to final state means it will be rejected. this is actually we called as dead configuration or trap state.

So coming to your question how we differentiate between DFA and NFA,

NFA say’s for every input alphabet in any state will have min = 1 transition and max = n (where n is total number of states) transitions possible.

DFA say’s for every input alphabet in any state will have exactly 1 transition.

Now think is Every DFA --- NFA or not

Note: we are differentiating between NFA and DFA on the basis of transiton function not on the basis of states, no doubt DFA has more states then NFA but that’s not the reason of difference. Reason of difference is transition function.

Hope the answer for the question

---

Sorry that doesn’t answer my question. Anyway I do not want you to type more. So, thank you.

---

gatecse Sir,

In $DFA$ , from each state for every symbol a transition is to be made,

but its not the case with $NFA$ as only the required transitions are present.

Thus a $dead$ $state$ is required in $DFA$ but not in $NFA$ (which is not a $DFA$).

Answer 2

This statement is wrong because DFA contain dead state .

Dead state simply a state in DFA in which if any input string reach than that string doesn't belong to that language.

Comments

what I understood is that,

Dead state /trap state : $(in$ $DFA)$

it is a state where on passing some invalid strings , some transitions reach there and then there is no way back to any other state and it will get stuck there.

Dead configuration : $(in$ $NFA$ $which$ $is$ $not$ $a$ $DFA)$

it is a configuration NOT  a state , and after passing some invalid strings, automata enters the dead configuration and ends  up rejecting the String.

But then according to this, the answer for this question will be $True$.

am i correct @gatecse Sir?

---

Im not able to see the first link and in the second link shared dead configuration is used in the context of NFA-- as a configuration from where no valid transitions are defined. If we go by this yes, DFA can't have dead configuration. But such definitions are "local" to a given book and you can't see them coming in standard exams like GATE.

---

gatecse

Okay Sir, Thankyou for clearing the confusion.