CMPUT 325 Special 7

Why not?

First note that we are not allowed
to write an

infinitely long program.

Since we can only assign constants
to 's'

it must be that 's' can only take
on a finite set of

distinct values (less than the number
of statements

in the code for example) .......
let us say N.

Recall that we cannot look ahead or
back up on

input ... So, we must read all the
a's before reading

the first b. Then we read all
the b's.

Now suppose there are K different
switch statements

in the code containing a 'getchar()'

When a 'b' is finally read there are
only NK possibilities:

One for each value of 's' and 'getchar()'
combination.

But these are the only means of knowing
how many

'a's were read (i.e. they are the
only things that distinguish

one run of a program from another
on different strings).

Since there can be many more than NK
a's in the string,

the program has no way of knowing
how many b's it should see.

(pigeon hole principle)

There is a formal method of proof called
the *pumping lemma*
* *which can be used in more general
contexts

and proves stronger results.