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).