1

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?

John Hoffman
  • 2,734

1 Answers1

3

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

André Nicolas
  • 507,029
  • 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 02: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 02: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 02:29
  • Thanks! But couldn't $y$ contain both $a$s and $b$s? Couldn't it also contain just $b$s? – John Hoffman Sep 29 '12 at 02:34
  • 1
    The $xyz$ is an initial section. – André Nicolas Sep 29 '12 at 02:37
  • Ohh... $xyz$ doesn't have to represent the whole string. Just any initial section of length at least $p$? Thanks a lot! – John Hoffman Sep 29 '12 at 03:44
  • 1
    @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 03:48