Timeline for First half of context-free palindromes
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 15, 2019 at 15:17 | comment | added | reinierpost | This is harder than I thought. I now know how to replace any right-hand side that generates only palindromes with a set of linear right-hand sides that generate the same language, but the original grammar may contain right-hand sides that do not generate only palindromes; it remains to be shown that this can be resolved by rewriting as well, but based on the lemmas needed for that, a much more direct proof is possible, so I will replace this answer with that. | |
| Feb 11, 2019 at 8:47 | comment | added | reinierpost | Indeed, I hadn't considered that case. I will improve this answer when I have time. | |
| Feb 10, 2019 at 13:26 | comment | added | Yuval Filmus | Counterexample: $S\to SS|00$. | |
| Feb 10, 2019 at 0:17 | comment | added | orlp | The issue lies in "What do its right hand sides look like? Each can contain only one nonterminal that generates a language with size > 1" . That is not true with my grammar. | |
| Feb 10, 2019 at 0:09 | comment | added | reinierpost | It's not linear. | |
| Feb 9, 2019 at 23:30 | comment | added | orlp | I definitely think you have the right idea but I think it needs to be formalized a bit better. E.g. the grammar $S \to SS \mid aa$ forms a palindromic language but does not conform to your argument. | |
| Feb 9, 2019 at 23:20 | history | answered | reinierpost | CC BY-SA 4.0 |