Theory of Computation - Finite Automata

Question

Can someone please help me understand these two points about minimum DFA and Minimum NFA, thank you

Comments

For the first one, recall that the transition function of a NFA is given as $Q$ x $\Sigma$ $\rightarrow$ $P(Q)$, where P is the power set. So, in the worst case the NFA might have $2^N$ states.

---

Oh then first point should be " if Min NFA has n states" right?

Answer 1

while converting NFA to DFA  number of states possible in DfA are between 1 to 2^n for n states NFA.

the same for the DFA if we have m states then the states in NFA could be log m to m states NFA.

Answer 2

If we use the subset construction method to build the DFA and if the NFA has $n$ states, then the states in the DFA can be any subset of the $n$ states and we know that the total number of subsets of $Q$ is given by $P(Q)$ which is the powerset of Q.

To put it another way, if $n$ is the number of states of the DFA, it has $2^n$ subsets of states. Each subset corresponds to one of the possibilities that the DFA must remember, so the DFA must contain at most $2^n$ states.

I am not sure what minimisation of NFA means - it is not known to have any simple algorithm.

Answer 3

for first statement->

NFA can have no transition for an input but for DFA there must be some transition so at max we need 2^n transition states.

for statement 2->

it is a reverse statement of first one NFA will have at max states equivalent to DFA