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?

Improve this question
$\endgroup$
7
  • $\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
    Commented Oct 10, 2016 at 10:04
  • $\begingroup$ Do you think that the language is context free or not? $\endgroup$
    – adrianN
    Commented Oct 10, 2016 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
    Commented Oct 10, 2016 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. ♦
    Commented Oct 10, 2016 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
    Commented Oct 11, 2016 at 5:40

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.