Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
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.
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.
