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:
NFA diagram Now the corresponding DFA diagram for this would be:

enter image description here 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}?

  • 2
    $\begingroup$ It looks to me like the NFA accepts strings whose next-to-last symbol is $0$. $\endgroup$ – saulspatz Jul 25 '18 at 17:11
  • 1
    $\begingroup$ Yes, but $\{q_0, q_1\}$ will be a single state of the DFA, so what's the problem? $\endgroup$ – saulspatz Jul 25 '18 at 17:17
  • $\begingroup$ @saulspatz , sorry for the late remark but, my confusion is, that from a input we end up into the state: {q0, q1} then, how is this one state? Are we in q0? or in q1? If not we're in both right? $\endgroup$ – bzal Jul 26 '18 at 5:38
  • $\begingroup$ $q_0,\ q_1$ are not states in the DFA, so we are in neither of them. You can think of the state in the DFA as the set of all NFA states we might be in on receiving the same input. $\endgroup$ – saulspatz Jul 26 '18 at 14:24

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\}\}$$

| cite | improve this answer | |
  • $\begingroup$ I can see the part here being deterministic, i.e. the transition function takes input to only one output, but it's still very unclear to me when we say that we're in state q'01 i.e. we're in {q0, q1} then what state are we in? are we in state q0? or are we in state q1? If we're in both, how come it's deterministic? $\endgroup$ – bzal Jul 26 '18 at 5:51
  • $\begingroup$ @bzal You should think of the state $q_{01}$ as a new state that nothing to do with the set $\{q_0,q_1\}$, besides it simulating a specific transition of the original NFA. You are neither in $q_0$, nor in $q_1$. You are in a completely new automaton with completely different states. (which has the property that it accepts the same language as your NFA). $\endgroup$ – Markus Peschl Jul 26 '18 at 13:23
  • 1
    $\begingroup$ @bzal In order to make a DFA out of an NFA, you have to generalise in a way. Let's say the states represent which country you are in right now: $q_0$ stands for Germany and $q_1$ for the Netherlands. In the corresponding DFA, let the states now represent continents and not countries anymore. Then you could think of $q_{01}$ as standing for the continent Europe and your transition function of the DFA takes one continent and returns another one, regardless of countries. $\endgroup$ – Markus Peschl Jul 26 '18 at 13:27
  • $\begingroup$ wow, that's a completely new understanding for me, and it's hard to grasp. How come there is no relation between the two FAs? I mean they have the same states,and following a DFA on inputs leads to exactly the same state as NFA... So, why no relation? In particular, I've been trying to answer this question: .... .. please see below: $\endgroup$ – bzal Jul 27 '18 at 5:14
  • $\begingroup$ Let's say in the NFA transition that state q0 is a state where 'w' the string has a zero, q1 is the state where 'w' as a 0 followed directly by 1 and q2 is a state where a 1 is followed directly by another 1. And let q2 be the accepting state, Now, for some transition diagram, we converted the NFA to DFA and in the time created a state called q'012 , So, how do we informally describe this state? Is this the state, where we can say the string now has a 0? or a 0 followed by one? or a string ending with 011? $\endgroup$ – bzal Jul 27 '18 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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