Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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\}$
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$.
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.
