Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
    
"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
1  
$\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

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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