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

  • $\begingroup$ "L must involve some kind of counting." -- how so? $\endgroup$
    – Raphael
    Commented Nov 1, 2012 at 14:27
  • $\begingroup$ @Raphael Are there non-regular languages that do not require counting? I'm not aware of any. $\endgroup$
    – Cat
    Commented Nov 1, 2012 at 17:07
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Nov 1, 2012 at 17:19
  • $\begingroup$ @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." $\endgroup$
    – Cat
    Commented Nov 1, 2012 at 17:29
  • 1
    $\begingroup$ $\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. $\endgroup$
    – Raphael
    Commented Nov 1, 2012 at 22:34

2 Answers 2


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


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


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.

  • $\begingroup$ Excellent answer, and great hints, though they didn't get me to quite the concise solution you did. Thanks! $\endgroup$
    – Cat
    Commented Nov 1, 2012 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" ...


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.