Question

Question: Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, and complement.

$$\begin{gathered} \mathit{a}\mathbf{.}\mathbf{}\left\{0^n{1}^m{0}^n|m,n⩾0\right\} \\ \mathit{b}\mathbf{.}\mathbf{}\left\{0^m{1}^n|m\ne n\right\}\mathbf{}\mathbf{}\mathbf{} \\ \mathit{c}\mathbf{.}\mathbf{}\mathbf{\left\{}\mathit{w}\mathbf{\right|}\mathit{w}\mathbf{\in }\left\{0,1\right\}\mathbf{*}\mathit{i}\mathit{s}\mathit{n}\mathit{o}\mathit{t}\mathit{a}\mathit{p}\mathit{a}\mathit{l}\mathit{i}\mathit{n}\mathit{d}\mathit{r}\mathit{o}\mathit{m}\mathit{e}\mathbf{\}}\mathbf{}\mathbf{} \\ \mathit{d}\mathbf{.}\mathbf{\{}\mathit{w}\mathit{t}\mathit{w}\mathbf{|}\mathit{w}\mathbf{,}\mathit{t}\mathbf{\in }{\left\{0,1\right\}}^{\mathbf{+}} \end{gathered}$$

Short answer

Answer:

a) $L=\left\{0^n{1}^m{0}^n|m,n⩾0\right\}$is not regular language.

b)$\left\{0^m{1}^n|mn\right\}$ is not regular language.

c)$\left\{w\right|w\in \left\{0,1\right\}*isnotapalindrome\}$is proved.

d) $\left\{wtw\right|w,t\in {\left\{0,1\right\}}^{+}$is not regular language.

Step-by-step solution

Pumping lemma for regular language.

Here the pumping lemma is used to find the language is regular language or not.

a. Assume B is regular language and their L is 0s and 1s. where, Z is belongs to L.

$$\begin{gathered} \left|z\right|⩾n \\ z=uvwxy \\ \left|v\right|⩾1 \end{gathered}$$

Here at least 1 is not null.

b. Find a suitable k so that so L is not regular language.

$$\begin{gathered} L=\left\{a^n{b}^n{c}^n\right|n⩾0\} \\ z=uvwxy \\ z=a^n{b}^n{c}^n\{n=1,z=abc\left\} \\ \right|z|=3n>n \end{gathered}$$

If we equate both z then we get,

$$\begin{gathered} uvwxy=a^n{b}^n{c}^n \\ \left|vx\right|⩾1,\{n⩾|vx|⩾1\} \end{gathered}$$

Then after that,

Let v or x is a part of -

$$\begin{gathered} \left(a^i{b}^j\right)or\left(b^i{c}^j\right) \\ v=\left(a^i{b}^j\right) \\ {v}^2=\left(a^i{b}^j\right)\left(b^i{c}^j\right) \\ u{v}^{2}w{x}^{2}y=a^m{b}^m{c}^m \end{gathered}$$

From this equation, it is proof that

$u{v}^{2}w{x}^{2}y\notin L$

Therefore,L is not regular language.

Language is regular or not.

a).

L=$\left\{0^n{1}^m{0}^n|m,n⩾0\right\}$

To prove that is not a regular language, we will use a proof by contradiction.

Assume that is regular. Then by the Pumping Lemma for Regular Languages, there exists a pumping length, for such that p for L any string $s\in L$where $\left|s\right|⩾p,s=xyz$subject to the following conditions:

$$\begin{gathered} \left(a\right)\left|y\right|>0 \\ \left(b\right)\left|xy\right|⩽p,and \\ \left(c\right)\forall i>0,x{y}^{i}z\in L. \end{gathered}$$

Choose$s=0^p{10}^p$. Clearly, $\left|s\right|⩾pands\in L$. By condition above, it follows that x and y are composed only of zeros. By condition , it follows that y = 0k for some k > 0. Per , we can take and the resulting string will still be in L. Thus, should be in .$x{y}^{0}z=xz=0^{\left(p-k\right)}{10}^p$ .

But, this is clearly not in L. This is a contradiction with the pumping lemma.

Therefore this assumption that L = $\left\{0^n{1}^m{0}^n|m,n⩾0\right\}$is regular is incorrect, and L is not a regular language.

Language is regular or not.

b).

$\left\{0^m{1}^n|m\ne n\right\}$

Let B =$\left\{0^m{1}^n|m\ne n\right\}$ Observe that B $B\text{'}\cap 0*1*=\left\{0^k{1}^{k}k⩾0\right\}.$If were regular, then would be regular and so would$B\text{'}\cap 0*1*$ . But we already know that$0^k{1}^{k}k⩾0$ isn’t regular, so cannot be regular. Alternatively, we can prove B to be non regular by using the pumping lemma directly, though doing so is trickier.

Assume that B =$\left\{0^m{1}^n|m\ne n\right\}$ is regular. Let P be the pumping length given by the pumping lemma. Observe the visible by all integers from 1 TO P,

where. $p!=p\left(p-1\right)\left(p-2\right)···1$Thus the pumping lemma implies that s can be divided as $xyzwithx=0a,y=0b,andz=0c1p+p!,whereb⩾1anda+b+c=p$. Let’s zero be the $stringxyi+1z,wherei=p!/b.Thenyi=0p!soyi+1=0b+p!,andsos0=0a+b+c+p!1p+p!.$But, this is clearly not in . This is a contradiction.

Hence,$\left\{0^m{1}^n|m\ne n\right\}$this is not a regular language.

Language is regular or not.

c).

$\left\{w\right|w\in \left\{0,1\right\}*isnotapalindrome\}$

To prove that L is not a regular language, we will use a proof by contradiction.

Assume that L is regular. Then by the Pumping Lemma for Regular Languages, palindrome is the string which contain same prefix and suffix there exists a pumping length, for such that P for L any string$s\in L$ where $\left|s\right|⩾p,s=xyz$subject to the following conditions:

$$\begin{gathered} \left(a\right)\left|y\right|>0 \\ \left(b\right)\left|xy\right|⩽p,and \\ \left(c\right)\forall i>0,x{y}^{i}z\in L. \end{gathered}$$

Then $w=a^{p}bb{a}^p$. Then $w\in L$. the task is now to show that we can "pump up" ww in such a way that the pumped word is no longer an element of.

Hence$\left\{w\right|w\in \left\{0,1\right\}*isnotapalindrome\}$,is proved

Language is regular or not. d).

$\left\{wtw\right|w,t\in {\left\{0,1\right\}}^{+}$

To prove that is not a regular language, we will use a proof by contradiction.

Assume that is regular. Then by the Pumping Lemma for Regular Languages, there exists a pumping length, for such that P for L any string$s\in L$ where $\left|s\right|⩾p,s=xyz$subject to the following conditions:

$$\begin{gathered} \left(a\right)\left|y\right|>0 \\ \left(b\right)\left|xy\right|⩽p,and \\ \left(c\right)\forall i>0,x{y}^{i}z\in L. \end{gathered}$$

Choose$s=0^p{110}^{p}1$ . Clearly s∈L with $w=0^{p}1andt=1,and\left|s\right|⩾p$. By condition , it is obvious that xy is composed only of zeros, and further, by and ,

it follows that $y=0^{k}forsomek>0$. By condition (c), we can take any will be in L. Taking $i=2,thenx{y}^{2}z\in L.x{y}^{2}z=xyyz=0^{\left(p+k\right)}{110}^{p}1.$There is no way that this string can be divided into $wtwasrequiredtobeinL,thusx{y}^{2}z/\in L$. This is a contradiction with condition of the pumping lemma. Therefore the assumption that is a regular language is incorrect and thus L$\left\{wtw\right|w,t\in {\left\{0,1\right\}}^{+}$ is not a regular language.