1
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – AABBCC
    Oct 21, 2019 at 16:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Oct 21, 2019 at 18:04
  • $\begingroup$ Now I understood your answer! Thanks for explaining it in detail. $\endgroup$
    – AABBCC
    Oct 22, 2019 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.