Question

Use the pumping lemma to show that the following languages arenot regular$\begin{array}{l}\mathbf{a}\mathbf{.}{\mathbf{A}}_{\mathbf{1}}\mathbf{=}\mathbf{\left\{}{\mathbf{0}}^{\mathbf{\eta }}{\mathbf{1}}^{\mathbf{\eta }}{\mathbf{2}}^{\mathbf{\eta }}\mathbf{\right|}\mathbf{n}\mathbf{\ge }\mathbf{0}\mathbf{\}}\\ \mathbf{b}\mathbf{.}{\mathbf{A}}_{\mathbf{2}}\mathbf{=}\mathbf{\left\{}\mathbf{\omega \omega \omega }\mathbf{\right|}\mathbf{\omega }\mathbf{\in }\mathbf{\{}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{\}}\mathbf{*}\mathbf{\}}\\ \mathbf{c}\mathbf{.}{\mathbf{A}}_{\mathbf{3}}\mathbf{=}\mathbf{\left\{}{\mathbf{a}}^{\mathbf{2}\mathbf{\eta }}\mathbf{\right|}\mathbf{n}\mathbf{\ge }\mathbf{0}\mathbf{\left\}}\mathbf{\right(}\mathbf{Here}\mathbf{,}{\mathbf{a}}^{\mathbf{2}\mathbf{\eta }}\mathbf{meansastringof}{\mathbf{2}}^{\mathbf{\eta }}\mathbf{a}\mathbf{\text{'}}\mathbf{s}\mathbf{.}\mathbf{)}\end{array}$$\begin{array}{l}\mathbf{a}\mathbf{.}{\mathbf{A}}_{\mathbf{1}}\mathbf{=}\mathbf{\left\{}{\mathbf{0}}^{\mathbf{\eta }}{\mathbf{1}}^{\mathbf{\eta }}{\mathbf{2}}^{\mathbf{\eta }}\mathbf{\right|}\mathbf{n}\mathbf{\ge }\mathbf{0}\mathbf{\}}\\ \mathbf{b}\mathbf{.}{\mathbf{A}}_{\mathbf{2}}\mathbf{=}\mathbf{\left\{}\mathbf{\omega \omega \omega }\mathbf{\right|}\mathbf{\omega }\mathbf{\in }\mathbf{\{}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{\}}\mathbf{*}\mathbf{\}}\\ \mathbf{c}\mathbf{.}{\mathbf{A}}_{\mathbf{3}}\mathbf{=}\mathbf{\left\{}{\mathbf{a}}^{\mathbf{2}\mathbf{\eta }}\mathbf{\right|}\mathbf{n}\mathbf{\ge }\mathbf{0}\mathbf{\left\}}\mathbf{\right(}\mathbf{Here}\mathbf{,}{\mathbf{a}}^{\mathbf{2}\mathbf{\eta }}\mathbf{meansastringof}{\mathbf{2}}^{\mathbf{\eta }}\mathbf{a}\mathbf{\text{'}}\mathbf{s}\mathbf{.}\mathbf{)}\end{array}$

Short answer

1. $A_1$is not a regular language.
2. $A_2$is not a regular language.
3. $A_3$is not a regular language.

Step-by-step solution

Introduction 

If A is the regular language and there is a number F ( the pumping length)

where S is a any string in A at least P length, then S may be divided into three pieces, $S=xyz$.

It satisfying the following conditions.

1. For each.$i\ge 0,xy\text{'}z\in A$

2.$\left|y\right|>0$, and

3. $\left|xy\right|\le p$.

The given language is A1={0n1n2n|n≥0} .

(a)

Assume A is a regular language.

Let P be the pumping length given by the pumping lemma consider a string$S=0^p{1}^p{2}^p\in A_1$.

$\left|S\right|>P$so, by pumping lemma, take$S=0^p{1}^p{2}^p\in xyz$such that$\left|xy\right|\le p,\left|y\right|>0$consider the following 2 possibilities:

Let$001122$be the string that belongs to$A_1$.$S=0^p{1}^p{2}^p=001122$. The pumping length of the string is 2. To satisfy the conditions of the pumping lemma,$x=0$, $y=0$,$z=1122$.

$\begin{array}{c}S=001122\\ =\frac{0}{x}\frac{0}{y}\frac{1122}{z}\end{array}$

Pump the middle part such that$x{y}^{i}z(i\ge 0)$. For$i=2$ , the Y becomes$00$. The string after pumping is$0001122$.

$\begin{array}{c}S=\left(0\right){\left(0\right)}^I\left(1122\right)\\ =\frac{0}{x}\frac{00}{y}\frac{1122}{z}[wheni=2]\end{array}$

The string$0001122\notin A_1$because the string that is accepted by the language should have equal number of 0 ’s, 1’s and 2’s. It is a contradiction. So, the pumping lemma is violated.

Therefore, $A_1$is not a regular language.

Consider the language,A2={ωωω|ω|{a,b}*} .

(b)

Assume$A_2$is a regular language.

Let P be the pumping length given by the pumping lemma.

Consider a string.$S=a^{p}b{a}^{p}b{a}^{p}b\in A_2$

By pumping lemma, this string can be divided into three pieces$xyz$such that$\left|xy\right|\le p,\left|y\right|>0$ and.$x{y}^{i}z\in A_2\forall i\ge 0$

So.$S=a^{p}b{a}^{p}b{a}^{p}b=xyz$

Let aabaabaab be the string that belongs to$A_2$. The pumping length of the string is 2. To satisfy the conditions of the pumping lemma,$x=a$,$y=a$,$z=baabaab$.

$\begin{array}{c}S=aabaabaab\\ =\frac{a}{x}\frac{a}{y}\frac{baabaab}{z}\end{array}$

Pump the middle part such that$x{y}^{i}z(i\ge 0)$. For$i=2$ , the Y becomes$aa$. The string after pumping is $aaabaabaab$.

$\begin{array}{c}S=\left(a\right){\left(a\right)}^{\text{'}}\left(baabaab\right)\\ =\frac{a}{x}\frac{a}{y}\frac{baabaab}{z}[wheni=2]\end{array}$

The string$aaabaabaab\notin A_2$ .It is a contradiction. So, the pumping lemma is violated.

Therefore, $A_2$is not a regular language.

Step 4:  A3={a2n|n≥0}(Here,a2n means a string of 2n a’s).

(C)

Assume that$A_3$is regular language.

Letbe the pumping length given by pumping lemma consider a string$\left|S\right|=a^{2p}\in A^3$. And$\left|S\right|>p$

By pumping lemma, this string can be divided into three pieces$xyz$such that$\left|xy\right|\le p,\left|y\right|>0$and$x{y}^{i}z\in A_2\forall i\ge 0$

Let aaaa be the string that belongs to$A_3$. The pumping length of the string is 2. To satisfy the conditions of the pumping lemma,$x=a$,$y=a$,$z=aa$.

$\begin{array}{c}S=aaaa\\ =\frac{a}{x}\frac{a}{y}\frac{aa}{z}\end{array}$

Pump the middle part such that $x{y}^{i}z(i\ge 0)$. For$i=2$ , the becomes aa. The string after pumping is aaaaa.

$\begin{array}{l}S=\left(a\right){\left(a\right)}^{\text{'}}\left(aa\right)\\ =\frac{a}{x}\frac{aa}{y}\frac{aa}{z}[wheni=2]\end{array}$

The string$aaaaa\notin A_3$.It is a contradiction. So, the pumping lemma is violated.

Therefore,$A_3$ is not a regular language.