Hi Ulrik Thank you, good to know.
I had missed that PEL formulation (very neat now that you point it out). Cheers, Peter. > On Oct 14, 2016, at 3:08 AM, Ulrik Rasmussen <ul...@utr.dk> wrote: > > October 14 2016 4:15 AM, "Peter Cashin" <cashin.pe...@gmail.com> wrote: >> Hi >> >> Yes, I seem to remember that Bryan Ford pointed out the “middle finder” >> grammar. >> >> It is CF but not PEG: >> >> s = x s x / x >> i.e an odd number of x’s. There is a similar one for an even number. >> >> I was interested to discover that this can be done with an extended PEG >> grammar. >> >> Cheers, >> Peter. > > That is also a PEL (parsing expression language, i.e. recognizable by a PEG), > you just have to rewrite it: > > <S> = xx <S> / x > > There is, as far as I know, no known examples of a CFL which cannot be > described by a PEG. The argument for "CF not-less-than PEG" instead relies on > a complexity result due to Lee[1] which says that a linear-time CFG parser > would imply the existence of an efficient O(m^2.333333...) algorithm for > boolean matrix multiplication. To the best of my knowledge, there is no proof > that such an algorithm cannot exist, but none has been found despite a > mountain of work on the subject. > > So, the question "CF < PEG?" is currently open: neither a formal proof nor a > counter-example has been found. > > [1] https://arxiv.org/abs/cs/0112018 > > > Regards, > > Ulrik Rasmussen > > _______________________________________________ > PEG mailing list > PEG@lists.csail.mit.edu > https://lists.csail.mit.edu/mailman/listinfo/peg _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
