tags:

views:

12

answers:

0
+1  Q: 

If a language (L) is recognized by an n-state NFA, can it also be recognized by a DFA with no more than 2^n states?

I'm thinking so, because the upper bound would be the 2^n, and given that these are both finite machines, the intersection for both the n-state NFA and the DFA with 2^n or less states will be valid.

Am I wrong here?

related questions

DVD menu coding
Using the DLR for (primarily) static language compilation...
Native Tongue as Default Language For an Application
Best technical shibboleths and keywords
What's with the love of dynamic Languages
What programs should I write to truly experience this fancy new language ?
Are there any examples where we *need* protected inheritance in C++?
What's wrong with C#?
How can I set LANG to ascii?
What is a language binding?
Factorial Algorithms in different languages
Suggestions on starting a child programming.
Introducing Python
What is the most unreadable programming language?
Is it worth it to learn an esoteric programming language?
What are your favorite "learning" projects, and why?
Tree-Based (vs. HTML-Based) Web Framework?
What's your favourite programming language, and its killer feature?
SICP ... better programming?
"Projects" for learning a new language
What if you used the wrong language?
What are the best resources on designing a new language?
How do you mark the maturation point of a programming language?
What is Turing Complete?
Multiple languages in an ASP.NET MVC application?