[Solved]: Number of Final States Subset Construction for NFA to DFA

Problem Detail: 

"Suppose we use the subset construction to convert a $7$-state NFA $M = (Q,\Sigma, \delta, q_0, F)$ into a DFA $M' = (Q', \Sigma, \delta', q_0, F')$ for the same language. Then $M'$ will have $|Q'| = 128$ states. If $|F| = 2$, then $M'$ will have $|F'| = 96$ final states."

From the subset construction, I know there are $\mathcal{P}(Q)$ new states in the machine, which means there are $2^7 = 128$ new states in $M'$. I am not sure mathematically why there are $96$ final states.

Observations:

I see that if I have an initial NFA with $3$-states $\{1,2,3\}$ and a $|F| = \{1\}$, then $P(\{1,2,3\}) = \left\{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \right\}$. I can also note that there are now $4$ final states and can conjecture $|F| = 2^{n} - 2^{n-k} = 2^{3} - 2^{3-1} = 4$, where $k$ is the number of final states. I also notice that each particular state occurs $2^{n} - 2^{n-k}$ times in the construction.

However, if I let there be $2$ final states (say $\{1,2\}$) in the initial machine, the new machine will have $5$ final states, not $2^3 - 2^{3-2} = 6$. I can see this is because $\{1,2\}$ is a state that contains both elements, and is being double counted.

I would prefer simple well-written intuitive answer rather than an overly mathematical one.

Asked By : Alex Luecke

Answered By : sjmc

Think about which states in the new NFA don't contain a state that was in $F$. These are $\emptyset$ and every combination of states from $\mathcal{Q}-F$, i.e. $\mathcal{P}(\mathcal{Q}-F)$.

In your 3-state example, the only elements of $\mathcal{P}(\{1,2,3\})$ that don't contain 1 or 2 are $\emptyset$ and $\{3\}$, which constitute $\mathcal{P}(\{3\})$, with cardinality 2, so we have $\mid F'\mid=8-2=6$.

For your 7-state example with $\mid F\mid=2$, the size of $\mathcal{P}(\mathcal{Q}-F)$ is 32, which means there are $\mid F'\mid=128-32=96$ states that also contain at least one state that was in $F$.

So your conjecture of $2^{\mid F\mid}-2^{\mid\mathcal{Q}-F\mid}$ is correct.

Best Answer from StackOverflow

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