FOM: expr. power of syntax

[Steve Stevenson]

Stephen:

I'm not even sure that you solved the multiple '~' problem, but you
have not yet shown the rules for every standard operator or something
like ~(p -> ~~q).

What is your grammar (as a post system/bnf ...) or function? This is
about the only way to really evaluate what the syntactic language
actually includes.

Unfortunately, I'm teaching a workshop right now and don't have enough
time to give a full tutorial, so maybe some other person with formal
languages can do better.

1. Regular languages have normal forms: (two, actually left or right
based on where the B is always first [I'd call this left] or B is
always last). A terminal has no "expansion rules" and a non-terminal
must have expansion rules.

   A -> tB
   A -> t

   where A, B are nonterminal and t is terminal.

2. Context free languages have normal forms:

   A -> BC
   A -> t

   A,B,C non-terminal

Example: integers can be recognized by a regular language

	  N -> dN
	  N -> 0 | N -> 1 | ....

Any language with an arbitrary nesting of parentheses is regular. In
my world, the language of arithmetic expressions is called ol'
faithful because it shows precedence *and* parens. To get arbitrary
nesting, you need to embed the start symbol. For ol' propositional faithful

	 E -> T \/ E | T
	 T -> F /\ T | F
	 F -> variables
	 F -> ( E )

(exercise to put into normal form)(exercise to add '->', etc)

Now, the syntactic expressive power would mean that two languages,
each generated by its own grammar, generate the same language. The
"language generated by a grammar" is the set of all terminal strings
that can be generated starting from a designated start symbol, in this
case 'E'.

Regular languages fail to capture the language generated by ol'
propositional faithful because they can't deal with *arbitrary*
nesting of parenthesized expressions.

  steve

 > 
 >  Stephen Fenner writes:
 >   > 
 >   > 
 >   > On Fri, 19 Jul 2002, Steve Stevenson wrote:
 >   > 
 >   > > >From what I see, you can't parse ~~~~~~~x1 or ~(p->v). Your "var"
 >   > > definition doesn't have to be that restrictive.
 >   > >
 >   > > steve
 >   > >
 >   > Steve,
 >   > 
 >   > Thanks, I should be clearer; I was writing quickly off the top of my head.
 >   > Here's what ~~~~~~~x1 naively translates to, for example (ignore whitespace):

<much stuff deleted>