CMPUT 325 Special 6

    Okay, this language can find patterns matching
    a regular expression (we have not proved this....)

    Clearly, anything this language can do, C (or JAVA etc)
    can do.
    Why?

    What about the other direction?
    Are there things we can do in C say, that cannot be done
    by this model?

    Yes, basically for example it cannot count.

    To illustrate: consider strings of characters of the form

        aaaaaa....aaaaabbbbbb....bbbbbbb

    Claim: this model cannot be used to
    write a program to determine if the number
    of a's is the same as the number
    of b's.  ( an easy task in C).

         NEXT