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.

         NEXT