Cheap and Secure Web Hosting Provider : See Now

# From NFA to DFA

, ,
Problem Detail:

Let $A = (Q,Σ,\delta,q_0,F)$ be an NFA such that $L = L(A)$.

We define a DFA $A'=(Q',Σ,\delta,q_0',F')$ as: $$Q'=2^Q, \qquad q_0'=\{q_0\}\\F'=\{q\in Q \mid q'\cap F \neq\emptyset\}$$ My question is how we know what elements $Q'$ has? What is the formal definition to obtain these elements? Because it can contain all elements of $2^Q$, and in the DFA obtained from a NFA, the states are not all the elements of $2^Q$.

#### Answered By : D.W.

In the DFA you defined, the states of this DFA are all the elements of $2^Q$.

There are other DFA's that might have fewer states, but those are different DFAs. For instance, in some variants of this construction, we only include the states that are reachable from $q'_0$ (we remove all states that can't be reached).

You might want to read, e.g., https://en.wikipedia.org/wiki/Powerset_construction and standard textbook explanations of the subset construction of a DFA from a NFA.

###### Best Answer from StackOverflow

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

3200 people like this