Question

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 $\mathit{p}\mathbf{\text{'}}\mathbf{⩾}\mathit{p}$The minimum pumping length for A is the smallest p that is a pumping length for A . For example, if $\mathit{A}\mathbf{=}\mathbf{01}\mathbf{*}$, the minimum pumping length is 2.The reason is that the string $\mathit{s}\mathbf{=}\mathbf{0}$is in A and has length 1 yet s cannot be pumped; but any string A in of length 2 or more contains a 1 and hence can be pumped by dividing it so that $\mathit{x}\mathbf{=}\mathbf{0}\mathbf{,}\mathit{y}\mathbf{=}\mathbf{1}\mathbf{,}\mathit{a}\mathit{n}\mathit{d}\mathbf{}\mathit{z}$is the rest. For each of the following languages, give the minimum pumping length and justify your answer.

$$\begin{gathered} \mathit{a}\mathbf{)}\mathbf{.}{\mathbf{0001}}^{\mathbf{*}} \\ \mathit{b}\mathbf{)}\mathbf{.}{\mathbf{0}}^{\mathbf{*}}{\mathbf{1}}^{\mathbf{*}} \\ \mathit{c}\mathbf{)}\mathbf{.}\mathbf{001}\mathbf{\cup }{\mathbf{0}}^{\mathbf{*}}{\mathbf{1}}^{\mathbf{*}} \\ \mathit{d}\mathbf{)}\mathbf{.}{\mathbf{0}}^{\mathbf{*}}{\mathbf{1}}^{\mathbf{+}}{\mathbf{0}}^{\mathbf{+}}{\mathbf{1}}^{\mathbf{*}}\mathbf{\cup }{\mathbf{10}}^{\mathbf{*}}\mathbf{1} \end{gathered}$$

role="math" localid="1660797009042" $$\begin{gathered} \mathit{e}\mathbf{)}\mathbf{.}\mathbf{(}\mathbf{01}\mathbf{)}\mathbf{*} \\ \mathit{f}\mathbf{)}\mathbf{.}\mathbf{\in } \\ \mathit{g}\mathbf{)}\mathbf{.}{\mathbf{1}}^{\mathbf{*}}{\mathbf{01}}^{\mathbf{*}}{\mathbf{01}}^{\mathbf{*}} \\ \mathit{h}\mathbf{)}\mathbf{.}\mathbf{10}{\left({11}^{*}0\right)}^{\mathbf{*}} \end{gathered}$$

$$\begin{gathered} \mathit{i}\mathbf{)}\mathbf{.}\mathbf{1011} \\ \mathit{j}\mathbf{)}\mathbf{.}\mathbf{\sum }^{\mathbf{*}} \end{gathered}$$

Short answer

1. Minimum pumping length four.
2. Minimum pumping length one.
3. Minimum pumping length four.
4. Minimum pumping length three.
5. Minimum pumping length two.
6. Minimum pumping lengthone.
7. Minimum pumping length three.
8. Minimum pumping length four.
9. Minimum pumping length five.
10. Minimum pumping length one.

Step-by-step solution

Define Pegion – hole principle

Pumping Lemma states, if n is the length of any string of length , the sequence of state $q1,q3,q20,q9,........q13$ has length $n+1$.

Because we know, n is at least p (where p is pumping length), and we know $n+1$ is greater than p, the number of states in the language. The sequence must contain a repeated state, fancy name of Pegion-hole Principle

If the string$Mdivideinxyz$ , then x goes from $r1torj,ytakesMfromrjtorjandz$ takes from $rjtorn+1$ and we know that $x{y}^{i}zfori⩾0andj⩾l,soy>0andl⩽p+1,so\left|xy\right|⩽p$

Determine the minimum pumping length of 0001*

(a)

Minimum pumping length four. Because every string need to be divided in at least three parts.

$x,y,z$Otherwise it cannot be pumped.

The minimum pumping length is four. The string 000 is in the language but cannot be pumped, so three is not a pumping length for this language.

If s has length four or more, it contains ones.

By dividing s into$X,y,z$ , where x is 000 and y is the first one and z is everything afterward, here satisfy the pumping lemma’s three conditions.

Minimum pumping lengthfour.Because every string need to be divided in atleastthreepartsx,y,z.Otherwise it cannot be pumped.

Determine the minimum pumping length of 0*1*

(b)

Minimum pumping length one.

The minimum pumping length is one. The pumping length cannot be zero because the string$\epsilon$ is in the language and it cannot be pumped.

Every nonempty string in the language can be divided into xyz, where $x,y,z$are $\epsilon$, the first character, and the remainder, respectively.

This division satisfies the all three conditions.

Determine the minimum pumping length of 001∪0*1*

(C)

Minimum pumping length three.

$aab+a*b*=\left\{aab\right\}\cup \{\epsilon ,a,b,a^2,b^2,ab,a^3,b^3,aab,abb,a^4,b^4,...\}$

$\{\epsilon ,a,b,a^2,b^2,ab,a^3,b^3,aab,abb,a^4,b^4,...\}$$=a*b*$

$p=1,$

This division satisfies the all three conditions.

Hence, the minimum pumping length one.

Determine the minimum pumping length of 0*1+0+1*∪10*1

(d).

Minimum pumping length three.

The minimum pumping length is three. The pumping length cannot be two 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 three.

If string is generated by$0*1+0+1*ands$begins either$0or11,$ write$s=xyz$ where x = ε, y is the first symbol, and z is the remainder of string.

If string is generated by$0*1+0+1*ands$ begins 10 , write $s=xyz$where x = 10, $s=xyz$ is the next symbol, and z is the remainder of string.

Breaking string up in this way shows that it can be pumped. If string is generated by $10*1$,

This division satisfies the all three conditions.

Here, we can write it as xyz where$x=1,y=0,andz$ is the remainder of string.

Determine the minimum pumping length of (01)*

(e).

$(01{)}^{*}=\{\epsilon ,01,0101,010101,(01{)}^4,(01{)}^5,...\}$

So starting from 01 we can set

$$\begin{gathered} \begin{array}{l}x=Z=\epsilon and \\ y=01\end{array} \end{gathered}$$

in the Pumping lemma. Hence,

$p=2,$the length of 01 .

This division satisfies the all three conditions.

Hence, the minimum pumping length is two.

Determine the minimum pumping length of ∈

(f).

ThisRegExrepresentsthelanguagethatonlycontainstheemptystring: $\{\in \}$.

There is no way of writing,

$\begin{array}{l}\epsilon =Xyzwith\\ y\ne \epsilon \end{array}$

so it suffices to let

p=1

The language is finite (and therefore regular), and there are nopump-able string.This division satisfies the all three conditions.

Hence, the minimum pumping length is one

Determine the minimum pumping length of 1*01*01*

(g).

$\{1*01*01*=\{00,100,010,001,1^{2}00,{01}^{2}0,{001}^2,1010,1001,0101,...\}$

Here, $1^0{01}^0{01}^0=00$isnotpump-able(ifpumpedthenitwouldproduce ${00}^{+}$whichisnotoftherequiredform$1*01*01*$.

However,allthestringsoflengththreearepump-ableproducing that is for example $1*00$from 100.

So,$p=3.$

This division satisfies the all three conditions.

Hence, the minimum pumping length is three.

Determine the minimum pumping length of 10(11*0)*0

(h).

$10(11*0)*0=\{100,10100,101100,1011100,1010100,...\}$

$100=10(11*0)00$isnotpump-able,

but $10100=10\left(1100\right)10$is pump-able producing $10100=10\left(10\right)*0$

So,$p=5$

This division satisfies the all three conditions.

Hence, the minimum pumping length is five.

Determine the minimum pumping length of 1011

(i).

This RegEx represents the language that only contains one string: $1011$.

If we pump any symbol then the length of the resulting string will be at

least five, so it cannot be a member of this language.

Hence, it suffices to

Let,$p=5$

The language is finite (and therefore regular), and there are no

pump-able strings. Andthis division satisfies the all three conditions.

Hence, the minimum pumping length is five.

Determine the minimum pumping length of ∑*

(j).

$\Sigma *=\{\epsilon ,...\}$is the language of all possible strings over the alphabet $\Sigma$.

This RegEx regular expression represents the language that only contains one string:$\Sigma *=\{\epsilon ,...\}$.

If we pump any symbol then the length of the resulting string will be at

least one,

so it cannot be a member of this language.

particular, if ais a symbol then a∗is also in Σ∗,

so, p=1

This division satisfies the all three conditions.

Hence, the minimum pumping length is one.