Timeline for Can the language of squares be described by a PEG?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 11, 2016 at 5:40 | comment | added | avakar | @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\}$). | |
| Oct 10, 2016 at 22:08 | comment | added | André Souza Lemos | Hypothesis: the language is inherently ambiguous, and if that is the case, then there is no PEG that defines it. | |
| Oct 10, 2016 at 20:55 | history | tweeted | twitter.com/StackCompSci/status/785584683358777345 | ||
| Oct 10, 2016 at 18:29 | comment | added | D.W.♦ | 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. | |
| Oct 10, 2016 at 12:15 | comment | added | avakar | @adrianN, I mean, is the solution obvious and I'm missing it? | |
| Oct 10, 2016 at 10:28 | comment | added | avakar | @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. | |
| Oct 10, 2016 at 10:12 | comment | added | adrianN | Do you think that the language is context free or not? | |
| Oct 10, 2016 at 10:04 | comment | added | avakar | 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. | |
| Oct 10, 2016 at 9:13 | history | asked | avakar | CC BY-SA 3.0 |