Problem understanding DFA & NFA equivalence in Theory of Computation

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!

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)\cup\delta'(\{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