Pumping Lemma More Examples

 Example

Regular — $L = (ab)^*$

Let $p$ be the pumping length (a DFA for $(ab)^*$ has 2 states, so $\mathrm{p\; can\; be\; taken\; as\; 2).}$

Pick $s = abab = (ab)^2$. Choose the decomposition

• $x=\epsilon,\ y=ab,\ z=ab$.
  Check: $|xy|=2 \le p,\ |y|=2\ge1$.
  Pump: for $i=\mathrm{2, }$$xy^2z = (ab)(ab)(ab) = (ab)^3 \in L$.
  (So the decomposition exists and pumping keeps the string in $L$.)

 Example

Regular — $L=(a{)}^{\ast }$

Proof.

1. Choose $p=1$. (Any fixed positive integer works; choosing 1 makes the argument simplest.)

2. Let $s\in a^*$ with $|s|\ge p=1$. Then $s$ is of the form $a^n$ for some $n\ge 1.$

3. Decompose $s$ as

   $$x=\epsilon,\qquad y=a,\qquad z=a^{n-1}.$$
   

   Then $|y|=1\ge1$ and $\mathrm{\mid }xy\mathrm{\mid }=1\le \mathrm{p.}$

4. For any $i\ge0$,

   $$xy^iz=\epsilon\cdot a^i\cdot a^{n-1}=a^{n-1+i}\in a^*.$$
   

   Thus every pumped string remains in $a^*$.

5. If $|s|<p$ (i.e. $s=\epsilon$

   ), the lemma’s requirement is vacuous because it only asserts something for strings of length 
   $\ge p$.

Hence a∗ satisfies the pumping-lemma conditions with pumping length p=1. 

$\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}\mathrm{}$

 Example

Non-regular — Palindromes over $\{a,b\}$

Let $p$ be pumping length. Choose

$s = a^{p} b a^{p},$

a palindrome. Decompose $s=xyz$ with $|xy|\le p,\ |y|\ge1$. Then $y$ lies entirely in the left block of $a$'s, so $y=a^k,\ k\ge1$. Pump with $i=0$:

$xz = a^{p-k} b a^{p},$

which has fewer $a$'s on the left than on the right, so it is not a palindrome. Thus $xz\notin L$

— contradiction. Palindromes are not regular.

 Example

L={a^nb^n∣n≥0}

Answer: Not regular.

Proof :
Assume $L_1$ is regular. Let $p$ be the pumping length. Take $s=a^{p}b^{p}\in L_1$ with $|s|\ge p$. By pumping lemma write $s=xyz$ with $|xy|\le p$, $|y|\ge1$. Because $|xy|\le p$, $y$ consists only of $a$'s, say $y=a^k$ with $k\ge \mathrm{1.\; Pump\; with }$$i=\mathrm{0: }$$x{y}^{0}z=xz=a^{p-k}{b}^{\mathrm{p. }}$This string has $\mathrm{<br>}$ $a$'s and $p$ $b$'s, so $xz\notin L_1$, contradicting the pumping lemma. Hence $L_1$ is not regular. ∎

 Example

Answer: Not regular.

Proof:
Assume regular and let $p$ be the pumping length. Choose $s=0^{p}1^{p}0^{p}$. Decompose $s=xyz$ with $|xy|\le p$, $|y|\ge1$. Then $xy$ lies entirely in the first block $0^p$, so $y=0^k$ with $k\ge1$. Pump with $i=0$: $xz=0^{p-k}1^{p}0^{p}$. Now the first and last zero-blocks have different lengths ($p-k$vs $p$), so $xz\notin L_2$. Contradiction ⇒ not regular. ∎

 Example

$L_{\mathrm{<br>}}=\{w\in \{0,1{\}}^{\ast }\mid \mathrm{\#}0(w)=\mathrm{\#}1(w)\}$

Answer: Not regular.

Proof :
Assume regular; let $p$ be pumping length. Choose $s=0^{p}1^{p}$. Decompose $s=xyz$ with $|xy|\le p$, $\mathrm{\mid }y\mathrm{\mid }\ge \mathrm{1.\; Then }$$y$ consists only of $0$'s (say $0^k$). Pump with $i=\mathrm{0: }$$xz=0^{p-k}1^{p}$ has fewer 0's than 1's, so $xz\notin L_3$. Contradiction ⇒ not regular.

 Example

L​={a^mb^n∣m=2n}

Answer: Not regular.

Proof :
Assume regular; let $p$ be pumping length. Choose $s=a^{2p} b^{p}$(so $m=2n$). Decompose $s=xyz$ with $|xy|\le p$, $|y|\ge1$. Since $|xy|\le p$, $y$ lies within the first $p$ $a$’s, so $y=a^k$ with $k\ge1$. Pump with $i=0$: $xz=a^{2p-k}b^{p}$. But now the number of $a$’s is $2p-k$, and condition $m=2n$ would demand $2p-k = 2p$⇒ $k=\mathrm{0,\; contradiction.\; Thus }$$xz\notin L_6$. Hence $L_6$ is not regular. ∎

L12​={anbm∣n is a multiple of m, m≥1}

is not regular. (I write $m\ge1$ because “multiple of $m$” is not meaningful for $m=0$.)

---

 Example

L​={a^nb^m∣n is a multiple of m, m≥1}

Proof (by Pumping Lemma)

Assume $L_{}$ is regular. Let $p\ge1$ be the pumping length given by the pumping lemma.

Choose the string

$$s = a^{p!}\,b^{p!}\in L_{12},$$

since $p!\; is\; clearly\; a\; multiple\; of$$p!$. Note $|s|=2p! \ge p$

By the pumping lemma write $s=xyz$ with

1. $\mathrm{\mid }y\mathrm{\mid }\ge \mathrm{1,}$

2. $|xy|\le p$,

3. $x{y}^{i}z\in L_{}$for all $i\ge0$.

From $|xy|\le p$ we see $xy$ lies entirely inside the first $p$ symbols of $s$, i.e. inside the first block of $a$’s. Therefore $y$ consists only of $a$’s:

$$y = a^{k}\quad\text{for some }k\text{ with }1\le k\le p.$$

Now pump with $i=\mathrm{2.\; The\; pumped\; string\; is}$

$$xy^{2}z = a^{p!+k}\,b^{p!}.$$

To belong to $L_{}$, the number of $a$’s (which is $p!+k$) would have to be a multiple of the number of $b$’s (which is $p!$). But $p!$divides $p!+k$ iff $p!$ divides $k$. Since $1\le k\le p$, $p!\nmid k$. Hence $p!\nmid (p!+k)$, so $a^{p!+k}b^{p!}\notin L_{12}$

This contradicts condition (3) of the pumping lemma. Therefore our assumption that ${\mathrm{<br>}}_{}$L​ is regular is false.

Example

Language. $L=\{a^{i^2}\mid i\ge 1\}$ (all unary strings whose length is a perfect square).

Claim. $L$ is not regular.

Proof (by pumping lemma).

1. Assume, for contradiction, that $L$ is regular. Then the pumping lemma gives a pumping length $p\ge1$.

2. Choose the particular string

   $$s = a^{p^{2}}\in L,$$
   

   since $p^{2}$ is a perfect square and $|s|=p^{2}\ge p$.

3. By the pumping lemma we can write $s=xyz$ with

   • $|y|\ge1$,

   • $|xy|\le p$,

   • and $xy^{i}z\in L$ for every integer $i\ge 0.$

4. From $|xy|\le p$ we know $xy$ lies entirely in the first $p$ symbols of $s$. Thus $y$ consists only of $a$’s, so

   $$y = a^{k}\quad\text{for some }k\text{ with }1\le k\le p.$$

5. Pump with $i=2$. The pumped string has length

   $$|xy^{2}z| = p^{2} + k.$$
   

   We will show $p^{2}+k$ is not a perfect square, so $xy^{2}z\notin L$, contradicting the pumping lemma.

6. Note that

   $$p^2<p^2+k\le p^2+p<p^2+2p+1=(p+1{)}^2\mathrm{.}$$

   Thus $p^{2}+k$ lies strictly between consecutive perfect squares $p^{2}$ and $(p+1)^{2}$, so it cannot itself be a perfect square.

7. Therefore $xy^{2}z\notin L$, contradicting the pumping lemma requirement that $xy^{i}z\in L$ for all $i\ge0$.

Hence our assumption was false and $L$ is not regular.

Example

L={0^n∣n is a power of 2} is not regular.

Proof :

Assume, for contradiction, that $L$ is regular. Let $p\ge1$ be the pumping length given by the pumping lemma.

Choose the string

$$s = 0^{2^{p}}\in L,$$

since $2^{p}$ is a power of $2$ and $|s|=2^{p}\ge p$.

By the pumping lemma we can write $s=xyz$ with

1. $\mathrm{\mid }y\mathrm{\mid }\ge \mathrm{1,}$

2. $|xy|\le p$,

3. $x{y}^{i}z\in \mathrm{L\; for\; every\; integer }$$i\ge 0.$

Because $|xy|\le p$, the substring $y$ lies entirely in the first $p$ symbols of $s$. Hence $y$ consists only of zeros:

$$y = 0^{k}\quad\text{for some }k\text{ with }1\le k\le p.$$

Now pump with $i=2$. The pumped string $xy^{2}z$ has length

$$|xy^{2}z| = 2^{p} + k.$$

We show $2^{p} + k$ is not a power of $2$. Indeed,

$$2^{p} < 2^{p}+k \le 2^{p}+p < 2^{p}+2^{p} = 2^{p+1},$$

because $k\le p < 2^{p}$. Thus $2^{p}+k$ lies strictly between consecutive powers of $2$, namely between $2^{p}$ and $2^{p+1}$, so it cannot be a power of $2$. Therefore $xy^{2}z\notin L$, contradicting condition (3) of the pumping lemma.

Hence our assumption that $L$ is regular is false.