2,996 views
1 votes
1 votes

Use the pumping lemma to show that the following languages are not regular.

  1. $A_{1}=\{0^{n}1^{n}2^{n}|n\geq 0\}$
  2. $A_{2}=\{www|w\in\{a,b\}^{*}\}$
  3. $A_{3}=\{a^{{2}^{n}}|n\geq 0\}$  $\text{(Here,}$$\text{$a^{{2}^{n}}$}$ $\text{means a strings of $2^{n}$ a's.)}$

1 Answer

1 votes
1 votes
According to the statement of Pumping Lemma:-

For any regular language $L$, there exists an integer $n$, such that for all $x ∈ L$ with $|x| ≥ n$, there exists $u, v, w ∈ Σ^{*}$, such that $x = uvw$, and
$(1) |uv| ≤ n$
$(2) |v| ≥ 1$
$(3) for \  all \ i ≥ 0: uv^{i}w ∈ L$

In Simple terms , it doesn't matter how many times sub string $v$ is pumped , the string would still belong to the language ,and if we can find some string $uvw$ such that on pumping $v$ , the string is not in the language then we can surely say that the language is not regular. Pumping Lemma is a negative test.

Let's take the 1st Language:-


$A1=\{0^{n}1^{n}2^{n}|n≥0\}$.

Let's take a string $w="001122" \in A1$.

In this string , let $u=00 , v=11,w=22$.

So according to pumping lemma , it doesn't matter how many times the string $v$ is pumped , the resulting string would still be in the language .

Let's pump $v$ once.

Resulting string= $"00111122"$.

But this string doesn't belong to $A1$ .  Thus pumping lemma fails here , thus we can say that the language is not regular.


Taking the next Language .


$A2=\{www|w∈{a,b}^{*}\}$.

Let us take a string $w=ababab$.

In this string , let $u=ab , v=ab,w=ab$.

So according to pumping lemma , it doesn't matter how many times the string $v$ is pumped , the resulting string would still be in the language .

Let's pump $v$ once.

Resulting string= $"abababab"$.

The resulting string doesn't belong to the Language , thus pumping lemma fails here , thus the language is not regular.


Taking the third one.


$A3=\{a^{2{n}}|n≥0\}$.

Let us take a string $w=aaaa$ which is $a^{2^{2}}$.

In this string , let $u=a , v=aa,w=a$.

So according to pumping lemma , it doesn't matter how many times the string $v$ is pumped , the resulting string would still be in the language .

Let's pump $v$ once.

Resulting string= $"aaaaaa"$.

But this string doesn't belong to $A3$ .  Thus pumping lemma fails here , thus we can say that the language is not regular.

Related questions