2
$\begingroup$

Given alphabet $\Sigma=\{a,b\}$, is the language $$L = \{ w \mid w\text{ contains an equal number of substrings }aa\text{ and }bb \}$$ regular? My initial though was no, because the language $L' = \{a^nb^n\mid n\ge0\}$, is not regular, and is of the same general form as $L$. However, I am confused about how $aa$ and $bb$ being substrings affects the proof, via pumping lemma. Is it proper to select a "specific" $s$ for the pumping lemma, such as

$$s = a^p(aa)^pb^p(bb)^p\,?$$

Is there a better $s$ I could choose? In general, how would I pick an $s$ when I am dealing with a language written based upon substrings, like $L$?

$\endgroup$
3
$\begingroup$

Your intuition is correct: regular languages can't count. Indeed, a quick way to prove that $L$ isn't regular is to observe that $L\cap \{a^mb^n\mid m,n\geq 0\} = L'\cup\{a,b\}$. Since the intersection of any two regular langauges is regular, and $\{a^mb^n\mid m,n\geq 0\}$ is certainly regular, it must be that $L$ is not – because if it was regular, then its intersection with $\{a^mb^n\mid m,n\geq 0\}$ would have to be regular, and it isn't.

To prove with the pumping lemma, you need to show that, for every $p>0$, there is a string $s$ of length at least $p$ such that every way of writing $s=xyz$ with $|y|\geq 1$ and $|xy|\leq p$ has $xy^nz\notin L$ for some $n\geq 0$. (I originally wrote "just need to show" but deleted "just" because the statement that follows is such a mouthful!)

Your string $s$ works just fine. If we rewrite it in the required form $s=xyz$, the fact that $|xy|\leq p$ means that $x=a^k$, $y=a^\ell$, with $1\leq\ell\leq p$ and $0\leq k\leq p-\ell$. And $z$ is the rest of the string. But, now, for any $n\neq 1$, we have \begin{align*} xy^nz &= a^ka^{n\ell}a^{p-k-\ell}(aa)^pb^p(bb)^p\\ &= a^{3p+(n-1)\ell}b^{3p}\,, \end{align*} and this string is not in $L$, since the number of $a$s at the front is different from the number of $b$s at the back, so the number of $aa$ substrings is different from the number of $bb$s.

Insofar as that proof works, there's no problem with your choice of $s$. But, if you read through the proof, you'll see that there would have been a bit less writing if you'd just chosen $a^pb^p$. The point is that, when something in the $a^p$ part gets "pumped", it breaks the required property of having the same number of $aa$s as $bb$s.

It's hard to give general advice, because proof is a creative act and you can't just follow recipes. The general scheme is to pick a string where repeating any sequence of characters from the first $p$ will break the property that defines the language.

$\endgroup$
  • $\begingroup$ thanks for all the help! To clarify is choosing $a^pb^p$, sufficient because in the case of an odd number of $a$ or $b$ characters, the one odd character would just not be considered part of a substring? For example, $aaaaaaabbbb$, the extra $a$ is not part of an $aa$ substring so there are 3 $aa$ substrings and 2 $bb$ substrings, and a single $a$? $\endgroup$ – tpm900 Feb 15 '17 at 1:23
  • $\begingroup$ @tpm900 No. The string $aaabb$ has two $aa$ substrings: the ones beginning at the first and second characters. These overlap but nothing in the definition of "substring" says that it can't overlap with another substring. So it's just the simple fact that $a^p$ has $p-1$ $aa$ substrings, which means that $a^mb^n$ has as many $aa$s as $bb$s if, and only if, $m=n$. $\endgroup$ – David Richerby Feb 15 '17 at 9:13
  • 1
    $\begingroup$ Tiny detail: both $a$ and $b$ are in the intersection but not in $L'$. Of course that's easily fixed. $\endgroup$ – Kai Feb 15 '17 at 22:09
  • $\begingroup$ @Kai Well spotted! Now fixed. Thanks! $\endgroup$ – David Richerby Feb 16 '17 at 8:48

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.