2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ INTERSECTION of a * b * not ab $\endgroup$ – bmc Oct 5 '16 at 17:30
  • 3
    $\begingroup$ 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. $\endgroup$ – D.W.♦ Oct 5 '16 at 18:36
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W.♦ Oct 5 '16 at 18:36
5
$\begingroup$

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?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I cannot find a string that is not in either! So does this mean that the intersecting language must be: a^n b^n? Then apply the pumping lemma to yield a contradiction and prove it is not regular? $\endgroup$ – bmc Oct 5 '16 at 18:04
  • $\begingroup$ 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. $\endgroup$ – orlp Oct 5 '16 at 18:08
  • $\begingroup$ Another question: Did you take this course as a computer science student, math student, or teach yourself? And do you just come on these forums to help others & keep your skills sharp? Or do you just enjoy the community? This place really is a miracle though lol & thanks again. $\endgroup$ – bmc Oct 5 '16 at 18:10
  • $\begingroup$ @bmc CS student. I help on CS because I use it myself and try to pay the favor forward. It also helps me to learn - I often answer questions that were just beyond my horizon before answering and I learn as I answer. $\endgroup$ – orlp Oct 5 '16 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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