FOM: expr. power of syntax

[Ben Abraham]

Hi,

	Here's a quick and dirty proof that the language of sentential
logic is not regular.

1) The most popular way to represent formulas is using infix notation. I
assume infix.

2) Infix notation requires parenthesis, they are not included in your set
of symbols but are required in order to resolve ambiguities.

Consider: a /\ b \/ c, with a=false b=false c=true

(a /\ b) \/ c is true a /\ (b \/ c)  is false

3) Now the parens must be balanced in a wff.
4) The most trivial expression with balanced parens is not regular
{(),(()), ((())), (((()))), ... }.
proof: use the pumping lemma for regular langs. in any text (this example
frequently used). you need a PDA (it is context free).
5) infix wff's are not regular

btw. a context free grammar for expressions is doable and easy.

On Wed, 17 Jul 2002, Thomas Forster wrote:

>
> Dear FOM-ers,
>              I ahve recently been putting the finishing touches to an
> undergraduate textbook on logic, and it has caused me to think quite
> hard about some issues i want to sell to the kiddies.  In it i make a
> big fuss about how essentially all the progress in modern logic became
> possible once one had the idea of separating syntax from semantics so
> that one could prove completeness theorems and the like.  We've had a
> lot to say over the last 100yrs or so about the expressive power of
> various kinds of syntax!  It then occurred to me that there is
> probably quite a lot that can be said along the following lines: we
> all know that regular languages (in the sense of Kleene) are pretty
> trivial - in the sense that not much can be said in them.  Polynomial
> notation for natural numbers seems to be about as good as it gets.  In
> particular it's obvious that the language of propositional logic is
> context-free not merely regular.  My question is: are there known
> theorems which capture this insight rigorously?  One could imagine a
> theorem along the lines ``There is no recursive (in the correct sense)
> map f from the set of all strings over {p,q,', /\, \/, ~} into any
> other language s.t. the image in f of the set of wffs is regular''.
>
>    Does anybody know of such theorems?   If not, i'll have a go at
> proving a few myself.....
>
>        Thomas Forster
>
>