Tuesday, April 03, 2018
Challenge: Is there a small NFA for { a^i : i\ne 1000} ?
(Added later- a reader left a comment pointing to a paper with the answer and saying that the problem is not original. My apologies- upon rereading I can see why one would think I was claiming it was my problem. It is not. I had heard the result was folklore but now I have a source! So I thank the commenter and re-iterate that I am NOT claiming it is my problem.)
Consider the language
{L = ai : i ≠ 1000 }
There is a DFA for L of size 1002 and one can prove that there is no smaller DFA.
What about an NFA? Either:
a) Show that any NFA for L requires roughly 1000 states
or
b) Show that there is a small NFA for L, say less than 500 states
or
c) State that you think the question is unknown to science.
I will reveal the answer in my next post, though its possible that (c) is the answer and the comments will convert it to either (a) or (b).
Feel free to leave comments with your answers. if you want to work on it without other information then do not read the comments.
Subscribe to:
Post Comments (Atom)
I think the answer has already been known: http://lics.siglog.org/lics00/short00/7.pdf
ReplyDeleteUniversal finite automaton recognizes the complement of this language (i.e. NFA recognizes this language) with \Theta(\sqrt(n)) states, where n=1000 for this language.
I can see a sqrt(n) upper bound using the Frobenius coin problem, I wonder if it's the same that you have.
ReplyDeleteOh well, I see by the time I got back from vacation, the solution has been posted and it's essentially the same...
ReplyDelete