1
$\begingroup$

I have moderate understanding of the lemma's use in prototypical examples like $0^n1^n$ and $WW$ (for any string $W$).

I have some confusion about the lemma's application to regular languages that don't appear to pumpable, though perhaps I'm mistaken somewhere. Suppose I define a language $L$ that can be expressed as the regular expression $1$. This language is clearly regular, because a (trivial) DFA can be constructed to accept it. The pumping lemma requires I define 3 strings, $x$, $y$, $z$, such that $L = xyz$. $z$ can be $ε$, but $y$ cannot be. There's no $xy$ I can come up with that has a $y$ that can be pumped whilst still being in my language.

This language appears to not be pumpable, and thus not regular, but I know it's regular for sure. Where's my mistake?

$\endgroup$
  • 1
    $\begingroup$ The pumping lemma states that every sufficiently long string in a regular language $L$ is of the form $xyz$ with $xy^i z\in L$ for all $i\geq 1$. The language $\{1\}$ you describe has no sufficiently long strings. $\endgroup$ – anomaly Feb 22 '16 at 5:44
  • $\begingroup$ What constitutes a "sufficiently long string"? $\endgroup$ – Alexander Feb 22 '16 at 6:00
4
$\begingroup$

The pumping lemma is vacuously true for finite languages, which are all regular. If $n$ is the greatest length of a string in a language $L$, then take the pumping length to be $n+1$: trivially, if $w\in L$ and $|w|\ge p$, then the conclusion of the pumping lemma holds (as does $0=0$, and $0=1$).

The language $\{1\}$ is pumpable: all strings in the language of length $\ge 2$ can be pumped.

The pumping lemma says something about infinite regular languages (their DFAs contain loops), and can be used to prove that various (necessarily infinite) languages are not regular.

$\endgroup$
  • 1
    $\begingroup$ okay I now understand that the pumping lemma only really pertains to infinite languages, but I'm unclear on the earlier part of your comment. "all strings in the language of length ≥ 2 can be pumped." Sure they can, but they'd no longer be in "1" $\endgroup$ – Alexander Feb 22 '16 at 6:41
  • 1
    $\begingroup$ Repeat: *all strings in $\{1\}$ of length $\ge 2$ can be pumped". There are no such strings in $\{1\}$, so whatever you say about them doesn't matter — the entire statement is true, "vacuously". It's also true that all strings in $\{1\}$ of length $\ge 2$ are such that $0 = 1$. $\endgroup$ – BrianO Feb 22 '16 at 9:09
  • 1
    $\begingroup$ oh yes, I got it $\endgroup$ – Alexander Feb 22 '16 at 10:29

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.