Question 1.55: The pumping lemma says that every regular language has a pum...
The pumping lemma says that every regular language has a pumping length p, such that every string in the language can be pumped if it has length p or more. If p is a pumping length for language A, so is any length p^{\prime } \geq p. The minimum pumping length for A is the smallest p that is a pumping length for A. For example, if A = 01^{*}, the minimum pumping length is 2. The reason is that the string s = 0 is in A and has length 1 yet s cannot be pumped; but any string in A of length 2 or more contains a 1 and hence can be pumped by dividing it so that x = 0, y = 1, and z is the rest. For each of the following languages, give the minimum pumping length and justify your answer.
{ }^{\text {A }} a. 0001^{*} f. \epsilon
{ }^{\text {A }}b. 0^{*} 1^{*} g. 1^{*} 01^{*} 01^{*}
c. 001 \cup 0^{*} 1^{*} h. 10\left(11^{*} 0\right)^{*} 0
{ }^{\text {A }} 0^{*} 1^{*} 0^{+} 1^{*} \cup 10^{*} 1 i. 1011
e. (01)^{*} j. \Sigma^{*}
(a) The minimum pumping length is 4. The string 000 is in the language but cannot be pumped, so 3 is not a pumping length for this language. If s has length 4 or more, it contains 1s. By dividing s into xyz, where x is 000 and y is the first 1 and z is everything afterward, we satisfy the pumping lemma’s three conditions.
(b) The minimum pumping length is 1. The pumping length cannot be 0 because the string ” is in the language and it cannot be pumped. Every nonempty string in the language can be divided into xyz, where x, y, and z are “, the first character, and the remainder, respectively. This division satisfies the three conditions.
(d) The minimum pumping length is 3. The pumping length cannot be 2 because the string 11 is in the language and it cannot be pumped. Let s be a string in the language of length at least 3. If s is generated by 0^{*}1^{+}0^{+}1^{*} and s begins either 0 or 11, write s = xyz where x= \epsilon , y is the first symbol, and z is the remainder of s. If s is generated by 0^{*}1^{+}0^{+}1^{*} and s begins 10, write s = xyz where x = 10,y is the next symbol, and z is the remainder of s. Breaking s up in this way shows that it can be pumped. If s is generated by 10^{*} 1, we can write it as xyz where x = 1, y = 0, and z is the remainder of s. This division gives a way to pump s.