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.
getchar() number
| State | 1 | 2 | 3 |
| 1 | 7 | 8 | 1 |
| 2 | 2 | 6 | 4 |
| 3 | 15 | 13 | 5 |
| 4 | 12 | 10 | 11 |
| 5 | 3 | 14 | 9 |
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.