# What is the computational power of Parsing Expression Grammars?

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.