Suppose we have for example N= 5 and
K = 3
(5 states and 3 getchar()'s)
Then NK = 15.
Suppose we have 16 different strings with
from 1 to 16 a's
We fill in a table of where and in
what state the first
'b' is encountered.
The string with 16 a's
must be in one of these table entries on the first 'b'
(or be in an infinite loop and never reach a 'b')
Suppose that entry is (2,3).
Now we can have two strings, one with 4 a's
and the other with 16. In both cases the program
will continue inn exactly the same manner after
the first 'b'. But clearly, only one of 4 or 16 can be
the correct number of b's.