1
$\begingroup$

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?

1 Answers 1

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

  • 0
    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?2012-09-29
  • 0
    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.2012-09-29
  • 0
    @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.2012-09-29
  • 0
    Thanks! But couldn't $y$ contain both $a$s and $b$s? Couldn't it also contain just $b$s?2012-09-29
  • 1
    The $xyz$ is an **initial** section.2012-09-29
  • 0
    Ohh... $xyz$ doesn't have to represent the whole string. Just any initial section of length at least $p$? Thanks a lot!2012-09-29
  • 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$.2012-09-29