# Why is my pumping lemma proof misleading?

I am trying to prove whether $L = \{s : s \text{ contains exactly 1 a}\}$ for the alphabet $\Sigma = \{a, b\}$is regular or not using the Pumping Lemma. I think it is regular because I can construct a simple deterministic finite automata that accepts it.

However, if $L$ is regular, then, by the Pumping Lemma, for any string $s \in L$ of length at least $p$, $xy^iz \in L$ for any $i \ge 0$. If $y$ happens to contain the string with that one $a$, then $xy^0z = xz \not\in L$. And... that makes $L$ not pumpable?

Where did I err here?

For any long enough word, there exists an initial section of that word which contains a "middle" section which is pumpable. For this particular language, that middle section can never contain the letter $a$.
• Oh... so you mean I don't get to chose what $y$ is? In other words, if I am to prove that a language is not regular, I must prove that no such $y$ exists? – John Hoffman Sep 29 '12 at 2:15
• That's right, you definitely don't get to pick what you called $y$. To prove that a language is not regular, you must show that whatever $y$ the system picks, repetition of that $y$ enough times will lead to a word that is not in the language. – André Nicolas Sep 29 '12 at 2:19
• @JohnHoffman: Here is a standard pumping lemma argument: the language $a^nb^n$ ($a$'s, then equal number of $b$'s) is not regular. For if it is, any long enough initial $xyz$ section has a middle section which is pumpable. Take $n$ beyond that "long enough." Then the initial section $xyz$ is all $a$'s, and by repeating the middle section $y$ we can spoil the equality of the number of $a$'s and $b$'s. – André Nicolas Sep 29 '12 at 2:29
• The $xyz$ is an initial section. – André Nicolas Sep 29 '12 at 2:37
• @JohnHoffman: You need to look up the version of the Pumping Lemma for regular languages that is in your course/book. Statements differ in minor ways, but are all equivalent. The standard statement uses initial substring. There exists an $N$ such that if the word $w$ (in the language) has length $\gt N$, then there exists an initial substring $xyz$ of $w$, with $y$ non-empty, such that $\dots$. – André Nicolas Sep 29 '12 at 3:48