Timeline for Is the language of all non-palindromes context-free?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 12, 2017 at 20:55 | comment | added | matheussilvapb | My teacher always asks to make grammars without $\varepsilon$ productions, I think that's a good exercise. | |
| Sep 12, 2017 at 20:35 | comment | added | Yuval Filmus | My grammar is context-free (some people disallow $\epsilon$ transitions so that a CFG would automatically be a CSG, but that's not the only choice possible). It is, however, extremely simple to get rid of the $\epsilon$ production. The resulting grammar is $S\to aSa|bSb|aTb|bTa|ab|ba$, $T\to aT|bT|a|b$. | |
| Sep 12, 2017 at 19:49 | comment | added | matheussilvapb | Thanks, your grammar is way simpler than mine, but I think the idea is the same. Actually your grammar is a type-0 grammar due to that $\varepsilon$-transition, I wonder if you can make it without that. | |
| Sep 12, 2017 at 19:43 | history | answered | Yuval Filmus | CC BY-SA 3.0 |