# $\{a^n b^n\} \cap \{a^*b^*\}$ regular or not?

I have been asked a very interesting question in preparation for my exam coming up. The question is as follows:

Is $L=\{a^n b^n : n \geq 0\} \cap \{a^*b^*\}$ regular or not?

Assume $L$ is regular. Then, $L^c$ should be regular as well. Thus, $L^c = \{a^n b^n : n \lt 0\} = \{\}$, so if I compliment the compliment, I should get $L = U$ (the universal set). So, then $L=\{a^n b^n : n \geq 0\} \cap \{a^*b^*\} \neq U$, because $L$ does not contain words of the form $baba$, or $baaaababa$, etc. Therefore the language is not regular.

Is this an acceptable answer for the upcoming exam? Does this persuade anyone?

• INTERSECTION of a * b * not ab – bmc Oct 5 '16 at 17:30
• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. – D.W. Oct 5 '16 at 18:36
• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – D.W. Oct 5 '16 at 18:36

The complement of $\{a^nb^n \mid n \geq 0\}$ is not $\{a^nb^n \mid n < 0\}$. And the complement of the complement should always equal the original set. The rest of your argument falls apart here.
As an example, abb is a string that is not $a^n b^n$, thus it should be in the complement of L.
To hint at an answer, is there any string $a^nb^n$ that is not $a^*b^*$? What does this say about the intersection of the two?
• Correct, the intersection is $a^nb^n$. The intersection with $a^*b^*$ is just to throw you a bit of a curveball, and you can use the standard pumping lemma proof after finding out the intersection. – orlp Oct 5 '16 at 18:08