Thursday, April 05, 2018

Challenge about NFA for {a^y : y\ne 1000} answered.

Recall that in a prior post I asked

Is there an NFA for  { ay : y ≠ 1000 } with substantially less than 1000 states.

I will now show that any NFA for this set requires 999 states, so essntially 1000. The proof uses Ramsey Theory. I will tell you the little bit of Ramsey Theory that you need.

NO- the above is false.

There is an NFA with 60 states.  I have a complete exposition here and I have a paper (with coauthors) on cofinite unary languages and NFA's here). Generally if you want to only avoid
an the NFA an be done in sqrt(n) + O(\log n) states, but requires sqrt(n) states.

I sketch the ideas here for the 1000.

Convention- `reject 988' would mean rejecting a988.

It is easy show the following:
For all n \ge 992 there exists x,y\in N such that n = 32x +33y

For all x,y  32x+ 33y is NOT = 991.

If you have  an NFA with a 33-loop and a shortcut so you can also to 32 and back to the start
state, this NFA

accepts all y ≥ 992

rejects 991

we have no comment on anything else.

So if you prepend 9 states to that NFA you will have an NFA that

accepts all y ≥ 1001

rejects 1000

How to get all the numbers < 1000?

Use mod 3, mod 5, mod 7, mod 11 loops that only accept if the number is NOT equiv to 1000
mod 3, 5, 7, 11, Since 3*5*7*11 > 1000 we have

if y is rejected then y ≤ 1000, but y \equiv 1000 mod 3*5*7*11, so must have y=1000.

so 1000 is the only reject.

Number of states: 1 + 33 + 3 + 5 + 7 + 11 = 60 states.

I think you can do this in 58, but what is the BEST you can do?
My paper has lower bounds of sqrt(n) so in this case 32.

This is a GREAT theorem to teach to students in a course that covers regular langs and also P vs NP since the students THINK that an NFA cannot do better - AH BUT IT CAN! - so it gives a concrete example of

lower bounds are hard since someone may come along with a very clever trick you didn't think of

This semester when I had the class VOTE on whether or not there was a small NFA

48 thought that ANY NFA would require around 1000 states

One of the best students proved this! or perhaps ``proved'' this

Only 2 students knew that it could be done with MUCH LESS than 1000 states- and those two are exceptions- one is co-author on the paper (and he tells me that he originally thought it required 1000 when I first showed him the problem) and one is someone who often goes to my old course websites looking for more information and problems to work on (I like that ambition!) and came across material on this. 

I tell them `you thought this was the last lecture on reg langs. It was not. it was the first lecture on P vs NP'


  1. Cicadas with a runway. Neat! If I understand correctly, one thing this highlights is the difference in complementarity between DFAs and NFAs. Students that think, "oh, I'll equivalently look for NFAs that *only* accept 1000" would have a hard time, right?

  2. There is a simpler proof. In this language, there are at least $1000$ distinct accepting suffix sets of the form $A_j = y_i$ for $i \neq j$.
    Note that all the sets $A_j$ are incomparable with respect to $\subseteq$.

    In any NFA with $n$ states, the set of accepting suffixes can contain at most $n$ pairwise-incomparable accepting suffix sets. Therefore, the NFA must contain at least 1000 states.

  3. That's fascinating. Now, if one consider the sequence mapping each n to the minimal number of states of an NFA that accepts {a^i | i ≠ n}, I wonder how many of these values we know exactly? Maybe it would make sense to add this to the OEIS...

  4. nice/great idea but surprising nobody has thought of this before. did you do a literature search? did turn up this ref which seems somewhat related. as is called in software engr its a sort of "design pattern"...

  5. Second Edition of my P vs NP efforts: