Cheap and Secure Web Hosting Provider : See Now

[Solved]: Can number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states?

, , No Comments
Problem Detail: 

As title says, can the number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states - that is if the NFA recognizes the same language as the DFA and has $n$ states, can DFA have more than $2^n$ states?

I think it is, and this is trivially. However Wikipedia seeems to write that it is not possible to have more than $2^n$ states. So comes the question.

Asked By : Huge

Answered By : Ran G.

it surely can, but it needs not. Using the powerset construction you can convert any $n$-state NFA into a DFA with at most $2^n$ states.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback