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.






at

3 comments:

  1. Abu2:35 PM, April 03, 2018

    I think the answer has already been known: http://lics.siglog.org/lics00/short00/7.pdf

    Universal 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.

    ReplyDelete
  2. dom1:17 PM, April 05, 2018

    I can see a sqrt(n) upper bound using the Frobenius coin problem, I wonder if it's the same that you have.

    ReplyDelete
  3. dom1:25 PM, April 05, 2018

    Oh well, I see by the time I got back from vacation, the solution has been posted and it's essentially the same...

    ReplyDelete