Thank-you. I was not sure whether it had been proven that there were CFL's
that cannot be described by a PEG or whether it was just conjectured.
Sounds like it is the latter, with the palindrome being an example of a CFL
that is believed to be not describable by a PEG.
Does this mean one of the following would be valuable?
(1) Proof that a palindrome cannot be described by a PEG.
(2) Proof that a palindrome can be described by a PEG.
Cheers,
David
-----Original Message-----
From: Arnar Birgisson [mailto:[EMAIL PROTECTED]
Sent: Wednesday, October 31, 2007 07:56
To: [EMAIL PROTECTED]; peg@lists.csail.mit.edu
Subject: RE: [PEG] CFG vs. PEG
I'm a bit rusty in all this (trying to get up to speed again), but in the
original paper by Bryan lists this as an open problem.
As for your palindrome question, a CFG (in EBNF) would be something of the
sort
S ::= aSa for all symbols a in Sigma
| epsilon
Isn't this easily translated to a PEG:
S <- aSa / bSb / ... / epsilon
where a,b,... is an enumeration of Sigma?
Arnar
-----Original Message-----
From: [EMAIL PROTECTED] on behalf of David Mercer
Sent: Tue 2007-10-30 23:20
To: peg@lists.csail.mit.edu
Subject: [PEG] CFG vs. PEG
I know of languages describable by PEGs but not CFGs (e.g., a^n b^n c^n),
but are there any CFL's that cannot be described by a PEG? My quick thought
is x x^R (where x is a sequence of symbols, and x^R is the reverse of x).
Cheers,
David
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
