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 am unsure whether I got the notion behind the pumping length correctly. I know its definition, and just want to make sure that I understood everything correctly.
Suppose we have an automata that accepts $0^{*}1^{*}$. The longest word accepted is $01$ without an iteration, whose length is $2$. So $n=2$, am I correct?
In case of $0......01^{*}$ where there are $n$ zeroes, the constant would be simply equal to $n+1$.
Is my thinking correct?
One thing that's worth pointing out is that there can be many lengths that satisfy the pumping lemma. In your example, setting the pumping length to 2 does satisfy the pumping lemma. And so does length 3, 4, 5, etc. I think what you're asking about is the minimum pumping length. The pumping lemma is generally used to show proof that a language is not regular, in which case it doesn't really matter what the minimum pumping length actually is, just that there is some finite pumping length.
Anyway, I believe that the minimal pumping length for 0*1* is actually one, not two. It's true that the 01 is the the longest word accepted without an iteration, but that's not precisely the definition of the pumping length. There are two possible words of length one: 0 and 1. Both of these words can be pumped, and as you've shown, any words of length two or more can be pumped. Therefore, any word of length one or more can be pumped, so the minimal pumping length is one.
For your second example, I assume you mean the language L = {0n 1* | n is a specified constant}. In that case I believe you're right that the minimum pumping length is n + 1. We can pump 0n1, but we can't pump 0n.
