1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

You have defined $Q'$ to be $2^Q$. Therefore, it is $2^Q$. It's possible that there are states that cannot be reached by any sequence of transitions from the start state but they're still states because they were defined to be states.

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