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

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

-
"L must involve some kind of counting." -- how so? –  Raphael Nov 1 '12 at 14:27
@Raphael Are there non-regular languages that do not require counting? I'm not aware of any. –  Eric Nov 1 '12 at 17:07
That depends of what you consider to be "counting". Consider $\{ww \mid w \in \{a,b\}^*\}$ and $\{\langle M \rangle \mid M\ \ TM, M(0) = 0\}$ which are both not regular. –  Raphael Nov 1 '12 at 17:19
@Raphael That's fair, though I'm not entirely familiar with the second one's syntax. My professor would also probably say the first one uses counting, since it's "some indeterminable string repeated exactly twice." –  Eric Nov 1 '12 at 17:29
$\langle M \rangle$ is an encoding of the Turing machine $M$ into a string. To your professor I say, "$\{w^k \mid w \in \{a,b\}^*, k \in \mathbb{N}\}$?" Or, in other words: the number of repetitions is irrelevant, the complexity of the language lies in repetition. –  Raphael Nov 1 '12 at 22:34

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.

-
Excellent answer, and great hints, though they didn't get me to quite the concise solution you did. Thanks! –  Eric Nov 1 '12 at 17:10

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.

-
Very good answer and definitely great information. The only reason I didn't accept this answer is that it was second. Thanks, though, this information is great! –  Eric Nov 1 '12 at 17:10