While learning about the pumping lemma, I came across the following question:

Given the language L is $ a^n(0|1)^* $ with $ c_0 \cdot c_1 = n $ , where $ c_0 $ indicates the amount of zeros present, use the pumping lemma to prove that this language is not regular. Examples of valid words in L are `0`

, `1`

, `a01`

, `aa001`

, etc…

In regular english: a word with leading `a`

s, followed by any amount of either `0`

or `1`

characters, where the amount of zeros multiplied by the amount of ones needs to match the amount of `a`

s.

My initial attempt was the following:

- Pick w as $ a^p0^p1 $ . This obviously holds since $ p \cdot 1 = p $ .
- Split w into xyz as $ x = \epsilon $ , $ y = a^p $ , $ z = 0^p1 $ .
- Show that $ xy^2z = a^{2p}0^p1 $ does not hold, since $ p \cdot 1 \ne 2p $ .

However, the answer key instead opts to introduce two new variables $ m \geq 0 $ , $ n \gt 0 $ , then splits on $ x = a^m $ , $ y = a^n $ , $ z = a^{p-n-m}0^p1 $ (splitting the sequence of a into three parts). Then, they too use $ i = 2 $ to show that $ xy^2z = a^{m}a^{2n}a^{p-n-m}0^p1 = a^{p+n}0^p1 $ , which is not a member of the language (since n was more than 0).

As far as I can see, my attempt adheres to the $ |xy| \leq p $ condition of the pumping lemma: x is empty and $ |y| = p $ . As such, I was under the impression that my answer was correct.

However, the huge increase in complexity of the answer in the answer key leads me to believe that this is not a valid approach. I have the sneaking suspicion this is because my answer actually *does* violate the $ |xy| \leq p $ condition.

Is my attempt a correct way to prove that the language is not regular? If not, what misconception/mistake did I make along the way?