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

  • 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