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$
2
  • 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
    Commented Feb 22, 2016 at 5:44
  • $\begingroup$ What constitutes a "sufficiently long string"? $\endgroup$
    – Alexander
    Commented Feb 22, 2016 at 6:00

1 Answer 1

Reset to default
5
$\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$
3
  • 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
    Commented Feb 22, 2016 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
    Commented Feb 22, 2016 at 9:09
  • 1
    $\begingroup$ oh yes, I got it $\endgroup$
    – Alexander
    Commented Feb 22, 2016 at 10:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .