Problem understanding DFA & NFA equivalence in Theory of Computation

ignougroup
Problem Detail: Before asking this question,I had gone through Equivalence of NFA and DFA – proof by construction but my question is a bit different from that. I was reading Michael Sipser’s Introduction to Theory of Computation and I came to a problem. I couldn’t understand as to how he is taking his act on equivalence between NFA and DFA. I have problem understanding this para :-

Next, we determine the start and accept states of D. The start state is E({1}), the set of states that are reachable from 1 by traveling along ε arrows, plus 1 itself. An ε arrow goes from 1 to 3, so E({1}) = {1, 3}. The new accept states are those containing N4’s accept state; thus {1}, {1,2}, {1,3}, {1,2,3}.

My assumption—> As {2} is not in the list of accepted states,so {1,2} should not be considered as new accept state in equivalent DFA.Also,{1} and {1,2,3} and {1,3} stand out as new accept states as per me because traversing from 1 to reasonable nodes lets the final accept state be reached—here,{1},accept state—>{1,3}—accept state as on inputting a from node 3 makes arrive at {1} which is an accept state,hence accpeted,and similarly for {1,2,3}. So,point at my wrong thinking PLEASE. I have understood that while making transitions only those states are considered final states which are accept states in NFA.Am I wrong???So,how come {1,2} be the new accept state in the equivalent DFA? Secondly, why he has mentioned that

The start state is E({1}), the set of states that are reachable from 1 by traveling along ε arrows, plus 1 itself`.

I couldn’t derive a meaning out of this statement,the reason might be my poor understanding of English language(I am non-native English speaker).Means start state is E({1})—fine upto here. Now, the set of states that are reachable from 1 by travelling along ε arrows,plus 1 itself—It doesn’t make any meaning standing as an independent sentence. Someone make me understand the meaning of this line,PLEASE! Someone please make me understand and elaborate a bit. I feel that author might be wrong there,pardon my noobiness or for any mistake! DFA-NFA Equivalence

Asked By : Am_I_Helpful

Answered By : Rick Decker

Motivation. In this construction, the intent is to make a DFA equivalent to a given NFA. In the original NFA, look at what happens when we’re in state 2 and we see input $a$: we could either stay in state 2 or make a transition to state 3. If we want to eliminate nondeterminism, we could say that from state 2 looking at input $a$ we move to the single new state ${2,3}$, meaning that in this case, we’re either in state 2 or state 3. In other words, in the constructed DFA we’ll have the transition $delta'({2}, a)={2, 3}$. The important thing to notice is that this transition in the new FA is deterministic: from the state ${2}$ on reading $a$ we move to the single state denoted by ${2, 3}$. Guided by this convention, we will build the DFA by defining the states to be all possible sets over 1, 2, 3, namely $$ emptyset, {1}, {2},{3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} $$ Final States. Let’s start with an example: what does the NFA do on input $baa$? We’ll have, in order

  1. In state 1, looking at $b$. Go to state 2.
  2. In state 2, looking at $a$. Go to state 2 or state 3.
  3. Looking at the last input, $a$ we could be in either state 2 or state 3. If we’re in state 2, go to state 2 or state 3 as before. If we’re in state 3, go to state 1.

In other words, at this stage, after having read $baa$ we could find ourself in states 2, 3, or 1. In the DFA, we have, equivalently, the transitions $delta’$ defined as

  1. $delta'({1}, b) = {2}$.
  2. $delta'({2},a) = {2, 3}$.
  3. $delta'({2, 3}, a) = delta'({2},a)cupdelta'({3},a) = {2, 3}cup{1}={1, 2, 3}$.

Now the question is, should state ${1, 2, 3}$ be considered as a final state? Sure, since the NFA, reading $baa$ has at lest one possible collection of transitions that leads to the accepting state 1. In a similar way, any state of the DFA containing 1 will be a final state, so in the DFA there will be four final states: $$ {1}, {1, 2}, {1, 3}, {1, 2, 3} $$ Now it turns out that in the DFA the state ${1,2}$ is never used, but that doesn’t negate the fact that it’s a final state (since it contains 1). All it means is that there is no transition that takes you there. It’s what we call an unreachable state. This, I hope, answers your first question. Start State. This answer to your first question has little to do with the answer to your second question. The answer for your second question is: just as we did to determine the final states of $D$, we also need to know what the start state of $D$ is, and in this case it will be the set of states containing the start state of $N_4$, along with any other states that can be reached from that start state via $epsilon$-moves, namely ${1, 3}$ (which of course will also be a final state, though that’s not important here).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28063