FOM: Expressiveness of Language I - Regular versus Context-Free

[Dennis E. Hamilton]

Re: http://www.math.psu.edu/simpson/fom/postings/0207/msg00038.html

I am not sure how deeply you want to go for the textbook you have in mind.
Perhaps an informal discussion may be sufficient.

1.	The regular languages are equivalent to the Chomsky finite-state
languages.  For example

pv ::= "p" | pv "q"

is a regular language, and its abstract syntactic forms are presentable as
sequence of nodes, the first node for "p", the next node for "pq", then for
"pqq", and so on until the end note, for whatever p or pq...q we have.

Although my intended interpretation of the pv language is as an enumeration
of propositional variables, it could also be  Peano numerals, etc.  It could
be successive complements of something.  Here, the presumption is that each
pv has interpretation as a unique, distinct entity.

(The use of two letters is to have pv be unambigous when used in pex, coming
up.)

2.	For the language of propositional logic, consider the simplification to
one primitive:

pex ::= pv | "/" pex1 pex2

pex1 ::= pex

pex2 ::= pex

where the two auxiliary productions are simply to give us a way to speak of
the two parts in the '"/" pex1 pex2' form.

Let the interpretation of '"/" pex1 pex2' be the logical nand of the
interpretation of the pex1 and of the interpretation of the pex2.

That pretty much gets to the essence of  propositional expressions, yes?

3.	Apart from sub-language pv, which is just a way to introduce a set of
labels for propositional variables, the language pex has, as the abstract
syntax, binary trees with a single kind of node and with the leaves
decorated with pv labels.

4.	It should be apparent, now, that if we insist on expressing a dyadic
operation, we must use a context-free language.  It is because pex1 and pex2
are arbitrary phrases of the proper form (which is what context-freeness is
all about) and an acceptor must have some expandable state to know that the
pex we are working on is to be followed by another pex or not.  The earlier
comment about parentheses of infix operations gets to the same situation.  I
think it stands out better here.

5.	I am assuming that to lose the distinguished dyadic operation would be to
undermine the (informal) notion of expressiveness of interest here.  That's
important.

Stay tuned ...

-- orcmid

------------------
Dennis E. Hamilton
http://orcmid.com/
mailto:dennis.hamilton at acm.org
tel. +1-206-932-6970
cell +1-206-779-9430
     The Miser Project: http://miser-theory.info