Below is a step-by-step explanation of how the Pumping Lemma for regular languages is being applied to show that a particular language (with the property (\lvert w\rvert_a = 2 \cdot \lvert w\rvert_b)) is not regular. I’ll assume the language is:
(That is, the number of s in any word is exactly twice the number of s.)
1. Pumping Lemma (brief recap)
If were regular, then there exists a “pumping length” (sometimes denoted ) such that any string with (\lvert s\rvert \ge n) can be decomposed into satisfying:
-
(\lvert xy\rvert \le n),
-
(\lvert y\rvert > 0), and
-
For all , the string .
To prove is not regular, you assume is regular and derive a contradiction by showing there’s at least one string in for which pumping (increasing or decreasing the number of copies of ) cannot remain in .
2. Choosing a String in
Given the pumping length , pick a specific string in that is long enough—usually something that clearly exhibits the “twice as many s as s” structure. A common choice is:
• Number of s: .
• Number of s: .
• Clearly, (\lvert w\rvert = 3n \ge n), so is a valid candidate for the lemma.
• Also, because and , so indeed .
3. Decomposing
By the Pumping Lemma, if is regular, then any decomposition with (\lvert xy\rvert \le n) and (\lvert y\rvert > 0) must allow pumping . But notice:
- (\lvert xy\rvert \le n).
Since starts with copies of b, that means and lie entirely in the first bs.
• In other words, is some (nonempty) prefix of .
• So consists only of bs. Suppose (\lvert y\rvert = k \ge 1). Then .
- (\lvert y\rvert > 0).
That ensures (the number of bs in ) is at least 1.
Hence, we can write:
where .
4. Pumping
The lemma says that for all integers , should remain in . Let’s check (pumping “up” once). Then the new string is:
[
x,y^2,z ;=; b^{m} ; \underbrace{b^k,b^k}_{b^{2k}}; b^{n - (m + k)},a^{2n}
;=; b^{m + 2k + (n - (m + k))}, a^{2n}
;=; b^{,n + k}, a^{2n}.
]
• Now the number of bs is .
• The number of as remains .
5. Checking Membership in
For to be in , we would need:
But (since ), so . Thus:
[
a\bigl(x,y^2,z\bigr) ;=; 2n,
\quad
b\bigl(x,y^2,z\bigr) ;=; n + k,
\quad
\text{so}
\quad
2n ;\neq; 2,(n + k).
]
Hence . This contradicts the requirement that all pumped strings remain in .
6. Conclusion
Because we found a string of length (the pumping length) for which the pumping property fails, our initial assumption—that is regular—must be false. Therefore, is not regular.
Why the Red Part?
In your notes, the “red part” likely refers to the step of pumping (i.e., replacing with ) and showing that the resulting string fails the condition (\lvert w\rvert_a = 2,\lvert w\rvert_b). That’s the crux of the contradiction:
-
You’ve identified that is some nonempty substring of the bs.
-
By doubling , you increase the count of bs but not the count of as.
That breaks the pumping lemma condition, proving non-regularity.
Summary
• We use the pumping lemma to assume the language is regular.
• We pick a carefully chosen string .
• We show that any valid pumping decomposition would force us to break the ratio of as to bs.
• Hence, the language cannot be regular.
In simpler terms: once you fix the ratio a = 2 * b, “pumping” extra bs (or removing some) will ruin that ratio.