1
$\begingroup$

Please help me with the following question:

Define the language LONGERB to be the set of strings over $\{a,b\}$ where the longest substring containing only $b$’s is strictly longer than the longest substring containing only $a$’s (e.g. $aabaabaaabbbba$ is in LONGERB because the longest substring containing only $b$’s has length 4 while the longest substring containing only $a$’s has length 3, while $ab$ is not in LONGERB). Let $n$ be the integer from the pumping lemma. How many of the following strings can be used in a pumping lemma proof that LONGERB is not regular?

(i) $abab^{n+1}$ (ii) $a^nb^{2n}$ (iii) $a^{10}b^{10}$ (iv) $a^nb^n$

The answer that has been given in the book is 3 (Options 1,2, and 4). But my doubt is, that the 4th option doesn't belong to the given language as there is an equal number of $a$'s and $b$'s in this option. So, according to me the correct answer should be 2 (Options 1 and 2 only).

Please give a proper reason for each of the four options, why it can or cannot be used to prove that the given language is not regular.

$\endgroup$
2
  • $\begingroup$ Only (i) and (ii) are actually in the language. But for pumping they should have the property that any regular pumping does lead outside the language. Only (ii) satisfies that condition, if we have the usual condition that pumping must occur within the first n symbols of the string. $\endgroup$ – Hendrik Jan Dec 24 '20 at 11:09
  • $\begingroup$ So, you are saying that only 2nd option is correct? @Hendrik Jan $\endgroup$ – Aman Rathore Dec 25 '20 at 6:24
1
$\begingroup$
  • Option 1: the word is in the language and it is of length $\geq n$, yet there is no guarantee that pumping it yields a contradiction. That is, the word can be used in the pumping lemma, but its not a good choice for proving non-regularity. Indeed, if $\text{LONGERB}$ is regular, then we know that there is a partition of $abab^{n+1}$ to three words, $xyz = abab^{n+1}$, where $|xy| \leq n$, $|y|> 0$, and $xy^iz\in \text{LONGERB}$ for every $i\geq 0$. Thus, if for example $y = ba$, then $xy^iz$ is indeed in $\text{LONGERB}$ for every $i\geq 0$ - so we cannot reach a contradiction to the assumption that $\text{LONGERB}$ is regular.

  • Option 2: the word is in the language and it is of length $\geq n$. Clearly it is good for pumping in the sense that it can be pumped for some $i$ so that $xy^i z \notin \text{LONGERB}$ - this is an easy exercise and the details are left to you.

  • Option 3: the word is of constant length that does not depend on the pumping constant $n$, so there is no guarantee that it is of length $\geq n$, so the pumping lemma says nothing about this word. Thus, we cannot use it to apply the pumping lemma on any language with a pumping constant $n$.

  • Option 4: you're right, the word cannot be used when applying the pumping lemma directly on the language $\text{LONGERB}$. However, it can be used to prove the non-regularity of $\text{LONGERB}$ indirectly by applying the pumping lemma on the language $\overline{\text{LONGERB}}$ which is the language of the words over $\{a, b\}$ where the longest substring containing only $b$’s is equal or shorter than the longest substring containing only $a$’s. Indeed, assume by contradiction that $\overline{\text{LONGERB}}$ is regular. If you consider the word $w = a^n b^n$, it is longer that $n$ and it is in the language $\overline{\text{LONGERB}}$. Then, there is a partition $xyz = a^nb^n$, where $|xy| \leq n$, $|y|> 0$, and $xy^iz\in \overline{\text{LONGERB}}$ for every $i\geq 0$. If you pump with $i = 0$, you get a contradiction. (BTW, I implicitly assumed that both a language and its complement have the same pumping constant $n$. This assumption is okay. Can you tell why?)

$\endgroup$
2
  • $\begingroup$ Thank you so much sir :) $\endgroup$ – Aman Rathore Dec 26 '20 at 13:04
  • $\begingroup$ @AmanRathore You're welcome. BTW, if you find the answer to be useful, you can also thank me by voting up or accepting the answer. This way, the answer also gets more attention for other users who are interested in the same question, and you might as well get your next badge. Welcome to the site :) $\endgroup$ – Bader Abu Radi Dec 26 '20 at 13:36

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.