Can there be a context free language that is not recognizable by a PEG?

This is related to this question. Essentially, I want to know whether my reasoning is correct.

1. We know that parsing with a context free grammar is same as boolean matrix multiplication (forward: Valient 1975, backward: Lee et al. 2002), and the latter has a lower bound of O(n^2) for arbitrary matrices.

If so, then there should exist a context free language $$L$$ such that any context free grammar that can represent it would take $$O(n^2)$$ for matching a string. This is because say there existed a grammar $$G_n$$ that allowed matches faster than $$O(n^2)$$ for any given CFL, then that grammar would allow faster multiplication for the corresponding Boolean matrices. Since Valient et al. and Lee et al. together shows that multiplication of BMs are same as parsing with a CFG, any BM can then be multiplied faster than $$O(n^2)$$, which is lower than the lower bound by theory.

2. So there should exist a context free language $$L$$ such that it takes at least O(n^2) time for checking membership in $$L$$.

3. PEGs are known to require only linear time (Birman and Ullman 1970), (Loff et al. 2019).

4. If there exist a PEG for $$L$$, it would be a recognizer that checks the membership in linear time, and hence, can solve matrix multiplication in linear time.

Hence, there does not exist a PEG for $$L$$.

Where am I going wrong?

Valient 1975

context-free recognition, for $$n$$ character input strings, can be carried out at least as fast as multiplication for $$n \times n$$ Boolean matrices

Lee et al. 2002

Any CFG parser with time complexity $$O(gn^{3-\epsilon})$$, where $$g$$ isthe size of the grammar and $$n$$ is the length of the input string, can be efficiently converted into an algorithm to multiply $$m\times m$$ Boolean matrices in time $$O(m^{3-\epsilon/3})$$.

Loff et al. 2019

In fact, the only method we know to prove that a language has no PEG is by using the time-hierarchy theorem of complexity theory: using diagonalisation one may construct some language $$L_2$$ which is decidable,say, in time $$n^2$$ (by a random-access machine), but not in linear time, and because PEGs can be recognised in linear time using the tabular parsing algorithm of Birman and Ullman  (or packrat parsing [32,33]), there will be no parsing expression grammar for $$L_2$$.

• @rahul: evidently, there are CFGs which can be parsed in linear time, despite Lee et al. Certainly, super-linear grammars exist. But you want to prove that there are languages which have no linear grammar. I haven't read Lee et al, but the abstract only talks about grammars. The quote from Loff et al. is convincing, but it's not based on converting between parsers and matrix multipliers.
– rici
Nov 30 '19 at 20:07
• So we know (via diagonalization) that there are CFLs without PEGs, but that doesn't identify any particular CFL, nor does it help us characterise a CFG whose language might be necessarily PEG-less. We do know that a super-linear language is not deterministic,.
– rici
Nov 30 '19 at 20:09
• @rici If we can say that that there are CFLs without PEGs, that is sufficient. This was the open question (as you answered here -- second part). Dec 1 '19 at 13:19

I see two flaws in this proof sketch, one related to CFLs vs CFGs, and another related to nested quantifiers and running time as a function of multiple parameters.

Any time you have a high-level proof strategy that seems to lead to surprising results, it is a good idea to check it carefully by expanding each step to obtain a detailed proof. Expand each claim with a precise statement, by applying the definition or the exact theorem in the literature, and verify carefully that they match up. This is particularly important when dealing with lower bounds, as they tend to introduce nested quantifiers that can lead your intuition astray when thinking only at a high level.

Flaw #1: CFLs vs CFGs

The proof seems to conflate context-free languages (CFLs) with context-free grammars (CFGs). However, there can be multiple CFGs that all generate the same CFL. At best, your proof strategy shows that there exists a CFG $$G$$ that can't be parsed by a PEG parser. But that's not surprising; we already know that PEG parsers can only parse CFGs that are in the PEG format. We cannot conclude anything about the corresponding CFL $$L(G)$$; for all we know, there might exist some other grammar $$G'$$ that is a PEG grammar and that yields the same language, i.e., $$L(G)=L(G')$$. Your proof doesn't rule that out, so it does not prove that the CFL it constructs can't be parsed by a PEG parser.

A concrete example of this is given at https://en.wikipedia.org/wiki/Parsing_expression_grammar#Expressive_power, which shows a simple CFG that cannot be parsed by a PEG parser, but where there exists another CFG for the same language that can be parsed by a PEG parser.

Flaw #2: Multiple parameters

It's important to expand out the statement of what is meant by these lower bounds. The lower bound on matrix multiplication means that, for each matrix multiplication algorithm, there exists an infinite family $$(A_1,B_1),(A_2,B_2),\cdots$$ of matrices such that $$A_n,B_n$$ are $$n\times n$$ matrices, and multiplying $$A_n \times B_n$$ using this algorithm takes $$\Omega(n^2)$$ time.

Lee's reduction describes how to construct a matrix multiplication algorithm from any context-free parser. If we now apply Lee's reduction to the matrix multiplication algorithm obtained from a PEG parser, we obtain an infinite family $$(G_1,w_1),(G_2,w_2),\cdots$$ of CFGs and inputs such that parsing them takes a long time. You'll need to dive into the details of Lee's reduction to determine the sizes of the $$G_n,w_n$$. Based on a quick look, it looks to me like the size of $$G_n$$ is $$\Theta(n^2)$$ and the size of $$w_n$$ is $$\Theta(n^{1/3})$$, but I'm not sure whether that's correct; you'd need to figure that out.

Next, you'd need to figure out the running time of a PEG parser, as a function of both the size $$g$$ of the grammar and the size $$n$$ of the input string. Standard references state the running time of a packrat parser for a PEG grammar as $$O(n)$$, but they don't describe the dependence on $$g$$; is it $$O(gn)$$? $$O(g^2n)$$? something else? You'd need to figure that out, and then apply it to the family above, to determine what the asymptotic running time of this parser is on the family $$L_n,w_n$$, and thus what the running time of this matrix multiplication algorithm is on the family $$A_n,B_n$$, to determine whether it contradicts the $$\Omega(n^2)$$ lower bound.

For instance, if the running time of a PEG parser is $$O(gn)$$, then Lee's reduction yields a matrix multiplication algorithm that takes $$O(n^{2.333\ldots})$$ time on the family $$A_n,B_n$$, which does not contradict the known lower bound.

Notice how Lee's result does not provide a single context-free grammar or context-free language where parsing is slow; it provides an infinite family of pairs of languages and inputs (which was not considered in your proof strategy). Also note the importance of getting the nested quantifiers right, and of capturing how the running time of a parser depends on both the size of the input and on the size of the grammar (which was not considered in your proof strategy). Hopefully this highlights how a strategy that sounds good can run into difficulties when one tries to apply it in detail; and one must check those details before assuming the strategy will work out.

• "At best, your proof strategy shows that there exists a CFG G that can't be parsed by a PEG parser." -- I do not see how this follows from my reasoning? I do not say anything about a particular grammar. Dec 1 '19 at 13:33
• For the Flaw 2, the point is that it does not describe the impact of the grammar right? I think that is a valid criticism. I will think it over, and understand the paper better, and get back. Dec 1 '19 at 13:41
• @rahul, You don't say anything about a grammar -- your proof sketch talks about languages -- but that is because your proof sketch conflates the two. In other words, that is exactly the flaw. If you checked carefully what step 1 actually guarantees, it is at best something about grammars, not something about languages. In other words, step 2 is flawed where it claims "So there should exist a context free language"; the correct statement would be "So there should exist a context free grammar" (well, really an infinite family of grammars, but that's beside the point).
– D.W.
Dec 1 '19 at 17:30
• I'm not entirely sure what you mean by "impact of the grammar", so I don't know if that is the point I was trying to make with Flaw 2. Hopefully you'll be able to read what I wrote and figure out if it matches what you are thinking.
– D.W.
Dec 1 '19 at 17:31
• I have added an explanation on step 1. which connects grammars in step 1 to languages in step 2. Does my explanation make sense? Dec 2 '19 at 5:08