Parsing Expression Grammars were introduced by Bryan Ford in Parsing Expression Grammars: A Recognition Based Syntactic Foundation.. Wikipedia says that it is an open problem to provide a Context Free language that can not be recognized by a PEG.

I am trying to understand the results from this paper -- The computational power of Parsing Expression Grammars by Loff et al. However, I am struggling to understand the notation used. What does the # mean in the following quote?

We show that PEGs are computationally "universal". Take any computational function $f: \{0,1\}^{*} \rightarrow \{0,1\}^{*};$ then there exist a computable function $g:\{0,1\}^{*} \rightarrow N$ such that

$\{ f(x)\#^{g(x)}x | x \in \{0,1\}^{*} \}$

has a PEG.

They use a slightly different symbol in Theorem 18.

$ L = \{ f(x){⧖}^{g(x)}x | x \in \{0,1\}^{*} \} \in PEG $

Where they talk about the $⧖$ as the number of symbols read (interpretation mine). How do I read this?

Further, can I take this to mean that the question whether a CFL exist that can not be recognized by a PEG is settled?

Essentially, if there exist a PEG for a P complete language, then all other problems in P can be reduced to it. Given that recognizing CFLs are in P, all CFLs should be reduced to recognizing this language.

Note that a similar question was asked by another user three years back, but this is new research.


$\#$ here is just a symbol; it has no special significance. (It's often used in the construction of an modified language to indicate a new symbol which is not in the alphabet of the original language.)

$\#^{g(x)}$ is, therefore, the unary encoding of $g(x)$; in that sense, it is a count.

The double-triangle used in the later proof is just another such symbol without special significance.

In response to your second question, the paper seems to be pretty clearly state (on page 4) that the question of whether there is a CFL with no PEG is still open. In particular, it is not known whether the language of even-length palindromes has a PEG, although it is certainly a CFL.

  • $\begingroup$ See my addition, is my reasoning faulty? $\endgroup$
    – rahul
    Nov 12 '19 at 14:22
  • $\begingroup$ @rahul: yes, I'm afraid it is faulty. The fact that you can reduce a problem to a different problem does not give you a parse of the original, since the transformation ("reduction") is not performed by the PEG itself. The case of palindromes is indicative. $\endgroup$
    – rici
    Nov 12 '19 at 16:30
  • $\begingroup$ could you please comment on this? cs.stackexchange.com/questions/117802/… $\endgroup$
    – rahul
    Nov 29 '19 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.