6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – avakar Oct 10 '16 at 10:04
  • $\begingroup$ Do you think that the language is context free or not? $\endgroup$ – adrianN Oct 10 '16 at 10:12
  • 4
    $\begingroup$ @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. $\endgroup$ – avakar Oct 10 '16 at 10:28
  • 3
    $\begingroup$ 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. $\endgroup$ – D.W. Oct 10 '16 at 18:29
  • 2
    $\begingroup$ @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\}$). $\endgroup$ – avakar Oct 11 '16 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.