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$.

  • $\begingroup$ 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? $\endgroup$ – John Hoffman Sep 29 '12 at 2:15
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Sep 29 '12 at 2:19
  • $\begingroup$ @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. $\endgroup$ – André Nicolas Sep 29 '12 at 2:29
  • 1
    $\begingroup$ The $xyz$ is an initial section. $\endgroup$ – André Nicolas Sep 29 '12 at 2:37
  • 1
    $\begingroup$ @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$. $\endgroup$ – André Nicolas Sep 29 '12 at 3: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.