0
$\begingroup$

What is the minimum pumping length for L=(0+1)1*0 ?

I'm guessing it's 2 (since it's shortest word is 00), but how do I then split into word = xyz and pump it so that it still stays in?

$\endgroup$
0
$\begingroup$

The word $00$ of length two you cannot pump yet, because the cycle $1^*$ does not contribute anything to it. What you can pump is any contribution of this cycle. You can see this from the lemma's proof which depends on cycles in the grammar/automaton. So three is the minimum pumping length.

In this case, you canalso pump the one in $10$, but this is coincidence, because $(0+1)$ and $1^*$ both produce $1$s. And since the lemma says "for all words longer than..." this does not change the minimum pumping length here, see $00$.

$\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.