Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ncar!tank!uxc!uxc.cso.uiuc.edu!m.cs.uiuc.edu!wsmith
From: wsmith@m.cs.uiuc.edu
Newsgroups: comp.lang.misc
Subject: Re: Syntactical defininition of English
Message-ID: <5200032@m.cs.uiuc.edu>
Date: 26 Oct 88 01:31:00 GMT
References: <726@wsccs.UUCP>
Lines: 22
Nf-ID: #R:wsccs.UUCP:726:m.cs.uiuc.edu:5200032:000:510
Nf-From: m.cs.uiuc.edu!wsmith    Oct 25 20:31:00 1988


>
>              x  y  z  y  x     (note: this requires a pushdown machine with
>	     a  b  c  b  a             multiple stacks, more power than an 
>				       automata equivalent to a CFL can be)
>

Don't you mean:
	  x   y   z   x   y
	a   b   c   a   b

instead?  (Technically, what you give is not a regular expression, either.)

The language you describe is generated by this context free grammar:

R ->   a R a | S ;
S ->   b S b | T ; 
T ->   T c   |   ;

Bill Smith
wsmith@cs.uiuc.edu
uiucdcs!wsmith