Consider the NFA that accepts the language L such that:
L={w| second last symbol in w is one}
Now, the NFA diagram for this is:
Now the corresponding DFA diagram for this would be:
Now, lets take an instance. Say we're at q0 state and we take an input 0, from the NFA we can see that we may be now at the q0 state or q1 state, and represent this in the DFA as q'01. This is where the confusion is, the resultant is a subset of the powerset of NFA's states.
By the definition of DFA, an input must result to only one state, so, when converting a NFA to DFA, why is it that the resulting state is a set and not just one state like q1 or q2 but like: {q0, q1}?
Best Answer
I understand where your confusion comes from. The proof that DFA's and NFA's are equivalent in terms of the languages they accept, involves something called "subset construction". In order to deterministically simulate all the states and transitions from the NFA, one has to build a DFA that so-to-say "lives" on the powerset of the state set $Q $.
However, it does not matter that our resulting states in the newly constructed DFA $D = \langle \mathcal{P}(Q),\delta,q_0,F\rangle $ are all sets, since the transition function $\delta : \mathcal{P}(Q) \rightarrow \mathcal{P}(Q)$ is still a real function (i.e it takes a state of $D$ - in this case a set - and returns exactly one other state (or in this case a set).)
Theoretically, the set of states of your original NFA could also be sets, or a set containing sets. It does not really matter what mathematical objects the set of states $Q$ consists of. The transition function of the DFA just has to be deterministic. If you go a bit deeper into the fundamentals of mathematics, you will see that even natural numbers can be seen as sets, for example the Von Neumann construction of the natural numbers works pretty much like this:
$$0 = \emptyset\\ 1 = \{\emptyset\}\\ 2 = \{\emptyset, \{\emptyset\}\}$$