I've been studying for an exam I have tomorrow, and I was looking through some previous sample exam questions, when I came across this problem:
Give a non-regular language $L$ such that $L \cup L^R$ is regular.
I've been sitting here and thinking and thinking, and I can't seem to come up with a situation where this is valid. I've determined a few things based on my understanding of non-regular languages, as well as the problem itself:
- $L$ must be infinite.
- $L$ must involve some kind of counting.
- $L$ must contain multiple letters (i.e. it cannot be composed of entirely $a$s).
Given this, I went through a few basic possibilities:
- $a^ib^i$ : This would result in $L \cup L^R$ being irregular also.
- $(ab)^i(ba)^i$ (or something else palindromic) : Again, this would result in $L \cup L^R$ being irregular also. (Any palindrome would, as $L = L^R$.)
- $a^pb^q$ (where $p$ and $q$ are prime) : This, too, would result in $L \cup L^R$ being irregular also, though it would be a very much broader language, which I think is a step in the right direction.
After I got this far, I think the key is in creating some language that, when unioned with itself, forms something akin to $a^*b^*$ or $(ab)^*$. The broader the words within the language, the easier it seems to define. But I can't seem to quite wrap my head around doing this.
Does anyone have a hint/spoiler or possible solution to this?
(NB: My professor does not post solutions.)