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.)
Find non-regular $L$ such that $L \cup L^R$ is regular?
formal languages;regular languages
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.