patternMinor
Is the emptiness problem for PEGs decidable?
Viewed 0 times
emptinessproblemthepegsdecidablefor
Problem
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.
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.
Solution
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.
A Recognition-Based Syntactic Foundation by Bryan Ford) actually contains a proof that emptiness is undecidable, indeed using the post correspondence problem.
Context
StackExchange Computer Science Q#143103, answer score: 6
Revisions (0)
No revisions yet.