How can I prove the minimum pumping length of finite language?

Let L be the set of all strings over {0, 1} whose lengths are at most three. Since L is regular, the pumping lemma holds for L, and thus there is a pumping length p associated with L. What is the smallest possible pumping length associated with L?

For this problem, I think minimum pumping length for this language should be 4, because if pumping length is smaller than or equal to 3, then $$xy^{i}z$$ may not be in the given language, because its length could be longer than 3. So, I want to prove that 4 is the minimum pumping length for the given language, but I have no idea how to prove it accurately. The explanation I wrote here is too informal, I think. Can anyone help me?

1 Answer

You explanation sounds good (you want to change "smaller than" in "smaller than or equal to").

Suppose towards a contradiction that the pumping length was $$k \le 3$$ then, since $$w=000$$ is a word of length at least $$k$$ in $$L$$, you could invoke the pumping lemma to conclude that $$w$$ can be written as $$w=xyz$$, with $$|y|>0$$, in such a way that $$xy^ik \in L$$ for any choice of $$i \ge 0$$.

This is a contradiction since the choice $$i=4$$ yields a word $$w'$$ of length $$|w'| = |x| + 4 |y| + |z| \ge 4$$ for which you simultaneously have $$w' \in L$$ (by the Pumping Lemma) and $$w' \not\in L$$ (by the definition of $$L$$).

In addition, to show that $$k'=4$$ is the smallest possible pumping length, you need to argue that $$4$$ is a valid choice for the pumping length. In your case this is trivial as the pumping lemma gives you a property over the set of all words in $$L$$ of length at least $$k'$$. For $$k'=4$$ this set is empty, which makes the statement trivially true.

• Thanks! It was really helpful. By the way, in some cases which use pumping lemma to prove that a infinite language is not regular(for example, $L$ = {$0^{n}1^{n}$ | $n $$\geq$$0$}), we show contradiction by giving a general example, like $0^{p}1^{p}$. But you gave a specific string as an example, in this case it is 000. Is it okay with finite language? Oct 21, 2019 at 16:28
• The word you use with the pumping lemma needs to be longer than some "pumping length" constant $n_0$. In general, when you prove that a language is not regular, you have no information on the value of $n_0$ and hence you provide a way to select an arbitrarily long word that is suitable for the proof. You can think of selecting $w= 0^n 1^n$ as "1) let $n_0$ be the constant of the pumping lemma statement for the language $L$; 2) pick any $n\ge n_0$; Consider the word $w=0^n1^n$; ...". In the answer we already know that $n_0\le 3$ and hence "000" has a length of at least $n_0$ and we can use it. Oct 21, 2019 at 18:04
• Now I understood your answer! Thanks for explaining it in detail. Oct 22, 2019 at 3:15