3
$\begingroup$

I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language $L=\{w\mid\#_{a}(w)=\#_{b}(w)\}$ and non-regular (simple proof using pumping lemma) implies that the language $L$ can therefore not be regular! The proof sounds alright initially but it got messy as I thought more on it! I read in the books that the subset property of a regular language is not closed under regular languages. So, how can the proof be correct because for all I know L is a regular language that a non-regular language $a^{n}b^{n}$ as its subset. How does it say anything more?

I do know ofcourse that $L$ here is not regular and can draw production rules for it(CFG)! But, I need to clear this confusion I have above! Some help me here.

$\endgroup$
4
$\begingroup$

Here is what your teacher meant. Let $M=\{a^nb^n:n\geq0\} $. We know $M$ is not regular. Since the intersection of regular languages is regular, if $L$ were regular then so would $L\cap a^*b^*=M$ be, reaching a contradiction. This shows that $L$ cannot be regular.

$\endgroup$
  • $\begingroup$ I agree -- that's probably what the teacher meant. $\endgroup$ – David Richerby Sep 13 '14 at 16:34
  • $\begingroup$ Now I see... Thanks for clearing it up!.. Yes, I must have got it wrong! $\endgroup$ – Ramit Sep 13 '14 at 19:48
  • $\begingroup$ Let's hope that's what they meant and said. $\endgroup$ – Raphael Sep 15 '14 at 10:15
3
$\begingroup$

You are correct: the fact that $L$ is a subset of a non-regular language does not prove that $L$ is non-regular. The trivial counterexample to that claim is the empty language, which is regular and is a subset of any language. (Similarly, proving that $L$ is a subset of a regular language also doesn't prove that $L$ is regular, since every language is a subset of the regular language $\Sigma^*\!$.)

Actually, I don't really understand why anyone would try to prove it that way. The direct pumping-lemma proof that $\{a^nb^n\mid n\geq 0\}$ isn't regular is hardly any more difficult than proving that $\{w\mid \#_a(w)=\#_b(w)\}$ isn't regular. Note also that demonstrating that a language is context-free doesn't prove that it's non-regular, since every regular language is context-free.

It occurs to me that you may have misunderstood your teacher's proof. Since the string $a^kb^k$ is in both langauges, you can prove that both langauges are non-regular by applying the pumping lemma to that string.

$\endgroup$
  • $\begingroup$ Okay, so how do I go about proving the fact that L is not regular? Note L here is the language having equal number of a's and b's $\endgroup$ – Ramit Sep 13 '14 at 13:40
  • $\begingroup$ Oh, sorry, I had the incorrect proof the wrong way around. But no matter: proving non-regularity of either of the two languages mentioned is just a straightforward application of the pumping lemma. Take the string $a^kb^k$ (which is in both languages) for $k$ large enough that the pumped section contains only $a$s. $\endgroup$ – David Richerby Sep 13 '14 at 13:45
1
$\begingroup$

We often use the Pumping Lemma for regular languages as the basis of a proof by contradiction.

The PL says that if $L$ is a regular language, then any sufficiently long word $w$ in $L$ can be written as $w=xyz$ (with certain restrictions on $x, y, z$) and can be pumped, namely that for all $i\ge 0$, we'll have $xy^iz\in L$. Now if that doesn't hold for a particular string in $L$ (i.e., for that particular word and for some particular $i$, the word $xy^iz\notin L$), then it must have been the case that our assumption, that $L$ was regular, must have been false.

In this case, pumping the particular string $a^pb^p$, where $p$ is the integer of the PL, gives you a string with more $a$s than $b$s, which can't possibly be in $L$, so $L$ couldn't possibly have been regular. In this case, we have a non-regular subset of a non-regular language: $E=\{a^nb^n\mid n\ge 0\}\subseteq L$. Roughly speaking, it's the way that $E$ behaves inside $L$ that says $L$ can't be regular.

On the other hand, if we had loosened the strictures of $L$ and instead had chosen another language $L_1=\{a, b\}^*$, then we'd have $E\subseteq L_1$ and now we'd have the non-regular $E$ as a subset of the regular $L_1$ (because the PL wouldn't yield a contradiction, no matter what string we tried, due to the way $L_1$ was defined).

$\endgroup$

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.