CMI2010-B-04c

Question

Indicate whether the following statement is true or false, providing a short explanation to substantiate your answers.

If a language $L$ is accepted by an NFA with $n$ states then there is a DFA with no more than $2^n$ states accepting $L$.

Answer 1

If a language $L$ is accepted by an NFA with $n$ states then there is a DFA with no more than $2^n$ states accepting $L$.

This is correct statement. With Proof.

Comments

I think your answer will be correct if $\left | \sum \right |=2$ i.e. only two alphabets were present (like 0,1).

In general it should be $\left | \sum \right |^n$. Please check before you believe.

---

@bhuv  $2^n$  is the number of states in the power set of $Q_{nfa}$, isn't it ? how is it related to number of input symbols ? as per my understanding, during subset construction, the new states introduced are from  members of the power set of $Q_{nfa}$ .And the power set can have $2^n$ possible combinations of states irrespective of number of alphabets in Σ ,isn't it ? Kindly explain your point little more.. 

---

From "Introduction to the Theory of Computation_MICHAEL  SIPSER", 

"If k is the number of states of the NFA, it has 2^k subsets of states. Each subset
corresponds to one of the possibilities that the DFA must remember, so the DFA
simulating the NFA will have 2^k states."

Here possibilities means either addition or removal (i.e. 2) of each state while we convert the NFA to its equivalent DFA , which simulates the NFA. So if NFA has k states, then its equivalent DFA goes up to maximum of 2^k states.

Answer 2

Because the DFA states consist of sets of NFA states, an n-state NFA may be converted to a DFA with at most 2ⁿ states. For every n, there exist n-state NFAs such that every subset of states is reachable from the initial subset, so that the converted DFA has exactly 2ⁿ states

https://en.wikipedia.org/wiki/Powerset_construction#Complexity 

Comments

converted DFA has exactly 2ⁿ states

it should be "not more than 2ⁿ"