# Can the language of squares be described by a PEG?

I believe that they can't, but I couldn't find any existing framework for parsing expression grammars akin to the pumping lemma that would allow me to prove it.

The language I'm talking about is

$$\{ww\mid w\in\{a, b\}^*\}$$

Can you help me prove it, or find a PEG grammar that parses the language?

• I search papers on PEG and I spent time thinking about it. But if you can give me some concrete direction, it would be greatly appreciated. – avakar Oct 10 '16 at 10:04
• Do you think that the language is context free or not? – adrianN Oct 10 '16 at 10:12
• @adrianN, it's not context free. I'm a bit confused by your question. This is not a homework and I've completed a CS major if that's why you're probing. – avakar Oct 10 '16 at 10:28
• Some useful background: it is known that there exist languages that are parseable by a PEG but aren't context-free (e.g., $\{a^n b^n c^n : n \in \mathbb{N}\}$). The class of languages accepted by a PEG is closed under union, intersection, and complement. It is an open question whether there exists any context-free language that can't be parsed by a PEG grammar; the original paper on PEG grammars conjectured that there does. See also cs.stackexchange.com/q/52224/755. – D.W. Oct 10 '16 at 18:29
• @AndréSouzaLemos, thanks, I see two problems. First, I believe I can produce non-erasing grammar for the language that has exactly one derivation for each string, second, there are inherently ambiguous languages that can be described by a PEG (e.g. $\{a^nb^mc^md^n\}\cup\{a^nb^nc^md^m\}$). – avakar Oct 11 '16 at 5:40