CMPUT 325 Special 7a

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.