Question $3$: Using the Pumping lemma to prove that the given language is not context free. $[3$ mark$]$ Language:

$\{$a$^$m b$^$n c$^($mn$)$ :m$>=0,$ n$>=0\}\{$a$^$n b a$^(2$n$)$ b a$^(3$n$)$ : n$=>0\}\{$a$^$n b$^$n a$^$n b$^$n :n$>=0\}$ define all ceses such like this: Cases $,A=\{a^n{b}^n{c}^n$:$n0\}$

Case $1$: The substring $vxy$ does not contain any $c.$

Consider the string $u{v}^{2}x{y}^{2}z=$uvvxyyz. Since $|vy|1,$ this string

contains more than $p$ many as or more than $p$ many $b$ s$.$ Since it contains

exactly $p$ many cs$,$ it follows that this string is not in the language $A.$ This

is a contradiction because, by the pumping lemma, the string $u{v}^{2}x{y}^{2}z$ is in

A$.$

Case $2$: The substring $vxy$ does not contain any $a.$

Consider the string $u{v}^{2}x{y}^{2}z=$ uvvxyyz. Since $|vy|1,$ this string

contains more than $p$ many $b$ s or more than $p$ many cs$.$ Since it contains

exactly $p$ many as$,$ it follows that this string is not in the language $A.$ This

is a contradiction because, by the pumping lemma, the string $u{v}^{2}x{y}^{2}z$ is in

A$.$

Case $3$: The substring vxy contains at least one a and at least one $c.$

Since $s=a^p{b}^p{c}^p,$ this implies that $|vxy|>p,$ which again contradicts the

pumping lemma.

Thus, in all of the three cases, we have obtained a contradiction. There$-$

fore, we have shown that the language $A$ is not context$-$free.

Complete the Example:

Show that $L=\{\begin{array}{c}{a}^n{b}^n{c}^n|n>0\end{array}$ is not a context free language by completing the following $($fill$-$in the blanks$)$:

First, assume that $L$ is a context free language. By the pumping lemma, there exists an integer $N_{?}$ which is the

pumping constant of $L.$ Consider the string $s=a^N{b}^N{c}^N$ in $L.$ The pumping lemma tells us that $s$ can be written in

the form $s=$uvxyz, where $u,v,x,y,$ and $z$ are substrings, such that $|vxy|N,|vy|1,$ and $u{v}^{i}x{y}^i$zinL for every

integer $i0.$

The possible decompositions can be summarized as:

Substring vxy contains only a$\text{'}$s$.$ Then $u{v}^{2}x{y}^{2}z$ will contain, more a$\text{'}$s than b$\text{'}$s and c$\text{'}$s

Substring vxy contains only b$\text{'}$s$.$ Then $u{v}^{2}x{y}^{2}z$ will contain, more b$\text{'}$s than a$\text{'}$s and c$\text{'}$s

Substring vxy contains only c$\text{'}$s$.$ Then $u{v}^{2}x{y}^{2}z$ will contain, more c$\text{'}$s than a$\text{'}$s and b$\text{'}$s

Substring $vxy$ contains a$\text{'}$s and b$\text{'}$s$.$ Then $u{v}^{2}x{y}^{2}z$ will contain less c$\text{'}$s than a$\text{'}$s and b$\text{'}$s

Substring vxy contains b$\text{'}$s and c$\text{'}$s$.$ Then $u{v}^{2}x{y}^{2}z$ will contain less a$\text{'}$s than b$\text{'}$s and c$\text{'}$s