0
$\begingroup$

"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.

$\endgroup$
  • $\begingroup$ $\{1\}, \{2\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}$ - that's $6$ states. $\endgroup$ – Karolis Juodelė May 11 '14 at 6:13
  • 1
    $\begingroup$ What does it mean to have an "overly mathematical" answer to a question that cannot be described as anything other than mathematics? $\endgroup$ – David Richerby May 11 '14 at 7:35
  • $\begingroup$ I meant use words. $\endgroup$ – Alex Luecke Jun 15 '14 at 20:59
4
$\begingroup$

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.

$\endgroup$

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.