FOM: expr. power of syntax

[Ben Abraham]

sorry for posting your personal reply steve, but i thought
in might clarify what i was trying to say.

On Wed, 24 Jul 2002, Steve Stevenson wrote:

> <snip>
>  >  in short regular expressions are bad at counting and when they do
>  > count they are ambiguous and without the right "semantic
>  > ingredients" we can't define an interpretation. so no such corr
>  > exists. sorry if i ran on a bit ...
>
> Yes, this is basically a limitation on regular languages. If they
> could count, they could balance parens...
>

yes, you can always pump out more leading parens in a correct expression
to get the balance wrong (analagous to the prefix notation arg given in
the post) but they can count things in a very elementary sense (for
example in "no paren infix"  notation they get the n op to 2n operand
ratio right, simply because of the adjacency of the operands to each
operator). i claim that when they can count they are amiguous so no corr
exists and an interpretation is impossible (not enought semantic
ingredients, namely the matching of operators and operands), i'm at work
now and haven't worked out the details ;-)