What is the computational power of Parsing Expression Grammars?

Question

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.

Answer 1

$\#$ 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.