# Is the emptiness problem for PEGs decidable?

The emptiness problem for Context Free Grammars is decidable. Does the same hold for Parsing Expression Grammars (PEGs)? That is, is it decidable given a PEG $$G$$ to find whether $$L(G) = \emptyset$$ or not.

My intuition says no, as PEGs are closed under intersection, allowing one to construct hard instances of intersection, but I haven't given the proof a lot more thought. The classic reduction to the PCP doesn't work I believe - at least simply replacing choice with ordered choice - as this changes what languages are accepted.

• Regrettably, I am not familiar with these grammars, but isn't ordered choice forcing the parse rather than the language? Aug 12, 2021 at 11:55
• @Hendrik Jan Consider $S = a / aa$ where $/$ is the ordered choice operator. In this case $L(S) = \{a\}$. Unintuitively $aa$ is not accepted because first $a$ is attempted which succeeds, thus the second choice is never evaluated.
– orlp
Aug 12, 2021 at 12:20
• Thanks. So the operator is like "greedy". I misunderstood, and thought is was more like "backtrack" (the parse does not fully succeed, so we try the alternative). Aug 12, 2021 at 12:54
• @HendrikJan It is backtracking, but only locally. It will never backtrack back over a successful (partial) parse even if later down the line it causes a failure. A positive side-effect of this is that PEGs are parsable in linear time.
– orlp
Aug 12, 2021 at 12:58

## 1 Answer

I should have done my research better before asking. The original paper introducing PEGs (Parsing Expression Grammars: A Recognition-Based Syntactic Foundation by Bryan Ford) actually contains a proof that emptiness is undecidable, indeed using the post correspondence problem.