Find non-regular $L$ such that $L \cup L^R$ is regular?

Question

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.)

Answer 1

Hint: try to come up with a language $L$, such that $L \cup L^R = \Sigma^*$.

Hint2:

Try to think on complements of known non-regular languages.

Solution:

Let $C = \{a^nb^n \mid n>0\}$, and define $L$ to be all the strings EXCEPT for those in $C$. That is, $L = \Sigma^*\setminus C$. It is easy to see that $L$ is not Regular (closure under complement). Now let's think about $L^R$. It contains all the strings in $\Sigma^*$, EXCEPT for strings of the form $b^na^n$.
Finally, $L\cup L^R = \Sigma^*$. Strings of the form $a^nb^n$ are not in $L$ but they are in $L^R$. Strings of the form $b^na^n$ are not in $L^R$ but they are in $L$.. al the rest of the strings appear in both languages. Since $\Sigma^*$ is regular, we are done.

Answer 2

Another quick solution: use two letters ($\Sigma = \{a,b\}$) and use $b$ only as a separator, then make $L$ irregular using a counting argument in such a way that in $L \cup L^R$ the counting argument "disappears" ...

Solution:

if $L = \{a^nba^m | n \geq m \}\;$, then $L^R =\{a^nba^m | n < m \} $
and therefore $L \cup L^R = \{a^*ba^*\}$

If your professor complains that there are too few $b$s out there (a cheat :-), then $L = \{a^nb^pa^m | n \geq m \}$ works equally well.