3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Regrettably, I am not familiar with these grammars, but isn't ordered choice forcing the parse rather than the language? $\endgroup$ Aug 12, 2021 at 11:55
  • $\begingroup$ @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. $\endgroup$
    – orlp
    Aug 12, 2021 at 12:20
  • $\begingroup$ 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). $\endgroup$ Aug 12, 2021 at 12:54
  • 1
    $\begingroup$ @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. $\endgroup$
    – orlp
    Aug 12, 2021 at 12:58

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

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.