[Solved]: Find non-regular $L$ such that $L cup L^R$ is regular?

ignougroup
Problem Detail: 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.)

Asked By : Eric

Answered By : Ran G.

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, $Lcup 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6418  Ask a Question  Download Related Notes/Documents