Google Answers: NFA yielding exponential size DFA

View Question

Q: NFA yielding exponential size DFA ( No Answer, 0 Comments )

Question

Subject: NFA yielding exponential size DFA
Category: Computers > Algorithms
Asked by: nr9-ga
List Price: $20.00

Posted: 24 Jun 2004 09:47 PDT
Expires: 24 Jun 2004 19:47 PDT
Question ID: 365647

What's a family of languages E_n where each E_n can be recognized by
an n-state NFA but requires at least c^n states on a DFA for some
constant c > 1 and how do you prove that E_n has this property?

Answer

There is no answer at this time.

Comments

There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.

Search Google Answers for

Google Home - Answers FAQ - Terms of Service - Privacy Policy