Minimum pumping length for the following regular languages

user2293062 picture user2293062 · Oct 9, 2015 · Viewed 10.7k times · Source

What are the minimum pumping length for the following languages ?

  1. The empty language
  2. (01)*
  3. 10(11*0)*0
  4. 1011
  5. 011 U 0*1*

Here are my solutions. Please correct me if I'm wrong.

  1. p = 0 because the language has no pumpable strings
  2. p = 2 because 01 is the shortest string that can be pumped
  3. p = 5 because 10100 is the shortest string that can be pumped
  4. p = 0 because string cant be pumped
  5. p = 1 because the string 0 can be pumped

I am not sure about my answers, so any help is appreciated. Thanks a lot!

Answer

Alec Brickner picture Alec Brickner · Jun 4, 2016

I think Simon's answer may be a little off. You do, in fact, need to take a cycle somewhere. The pumping lemma requires that the path taken to recognize the string include a cycle (this is the 'y' of the pumping lemma's 'xyz'). We can take this cycle as many times as we want, which pumps the string.

  1. This should be 1. The minimum pumping length must always be greater than 0, even if there are no strings in the language.
  2. This should be 2. If p = 1, we can't pump 01 (because y must equal 0, and 001 is not in the language).
  3. This should be 5.
  4. This should also be 5. If we set p=4, then we claim "1011" is pumpable (which it is not, as it is the only string in the language).
  5. p = 1.