1
$\begingroup$

I would like to know why the pumping length of language {a} is $2$ as said in this chat discussion.

Eventhough this discussion proves trivially that the pumping length of language {a} is $2$ I couldn't get by an example how the pumping length of language {a} becomes $2$.Could anyone help me with an example.

$\endgroup$
  • 1
    $\begingroup$ I'm assuming you mean minimal pumping length. Nevertheless, if your pumping length is $2$, then it must hold for every string in your language which length is at least the pumping length that.. etc etc. Your language doesn't even have strings of length at least $2$. Choosing a pumping length of 2 doesn't even make sense. Also, your language is finite so it is trivially regular (assuming you're talking about the pumping lemma for regular languages). $\endgroup$ – Auberon Mar 9 '16 at 10:32
  • $\begingroup$ @Auberon:Sorry but I'm not sure about that.I think that in this question there isn't a deal on whether it's pumping length or minimum pumping length. $\endgroup$ – justin Mar 9 '16 at 10:47
5
$\begingroup$

Informally, the pumping lemma for regular languages state that any sufficient large string may be pumped.

Your language is finite, meaning if you pick a pumping length that is larger than any string in your language, the lemma is trivially true. In your example the pumping length is $2$ but there are no strings in your language of length at least two. So you can pump all strings of length $2$ or longer (there are none!).

If you try and pick a smaller pumping length (the only possibility is $1$) then you will find that you can not pump. $w = a$ is your only string and the only possible decompsition $w=xyz$ is $x=\epsilon$, $y=a$, $z=\epsilon$. You can't however pump that because e.g. $\epsilon$ and $aa$ is not in your language.

Therefore; $2$ is the minimal pumping length of the language $\{a\}$

$\endgroup$
  • $\begingroup$ :This line "So you can pump all strings of length $2$ or longer (there are none!)." you have told gives the best explanation to this question.I couldn't get before that there were no strings of length $2$ or longer.Can you pump strings of length $0$? $\endgroup$ – justin Mar 9 '16 at 10:55
  • $\begingroup$ No you can not because in your decomposition $w=xyz$, $y$ must have a length of at least $1$. $\endgroup$ – Auberon Mar 9 '16 at 10:58
  • $\begingroup$ :I couldn't get why we can pump strings of length $2$ or longer if the strings presented by this condition are of length $0$. $\endgroup$ – justin Mar 9 '16 at 11:00
  • $\begingroup$ There are no strings of length at least $2$. So especially not empty ones i.e. of length $0$! $\endgroup$ – Auberon Mar 9 '16 at 11:04
  • 1
    $\begingroup$ That is correct. $\endgroup$ – Auberon Mar 9 '16 at 11:09
3
$\begingroup$

If you look at the proof of the pumping lemma, then you will see that the pumping length is nothing else than the number of states in the minimal finite automaton accepting the language. Your language is accepted by an NFA having $2$ states, so the pumping length is $2$.

$\endgroup$
  • $\begingroup$ What do you mean by the pumping length. Additionally, his language is accepted by an NFA with 5,6,7 or a million states. Did you mean a minimal DFA? $\endgroup$ – Auberon Mar 9 '16 at 11:16
  • 1
    $\begingroup$ @Auberon I meant what I wrote, minimal finite automaton. The proof actually works even for NFAs with multiple starting states, and for this class of automata there isn't necessarily one unique minimum. $\endgroup$ – Yuval Filmus Mar 9 '16 at 12:25
  • $\begingroup$ I see I read over the minimal part. $\endgroup$ – Auberon Mar 9 '16 at 12:28
2
$\begingroup$

If any string of length 2 is pumped, you obtain an even longer string. The original one as well as the new one are outside the language, everythign is fine.

If you pump the string a from the language, you obtain a longer one and are now outside the language. Thus length one does not work.

$\endgroup$

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.