edited by
1,109 views
0 votes
0 votes

Use the pumping lemma to show that the following languages are not context free$.$

  1. $\{0^{n}1^{n}0^{n}1^{n}\mid n\geq 0\}$
  2. $\{0^{n}\#0^{2n}\#0^{3n}\mid n\geq 0\}$
  3. $\{w\#t\mid w$ $\text{ is a substring of}$ $ t,$ $\text{where}$ $ w,t\in\{a,b\}^{*}\}$
  4. $\{t_{1}\#t_{2}\#...\#t_{k}\mid k\geq 2,$ $\text{each}$ $ t_{i}\in\{a,b\}^{*},$ $\text{and}$ $ t_{i}=t_{j}$ $\text{ for some}$ $ i\neq j\}$ 
edited by

1 Answer

0 votes
0 votes

The pumping lemma for CFL states: If $L$ is context-free, then there exists a positive integer $P> 0$, such that for any $x\in L$ with $\left | x \right |\geq P$, there exists $v,w,x,y,z$ such that $u=vwxyz$, $\left | wxy \right |\leq P$, $\left | wy \right |> 0$ and $\forall m\geq 0$, $uw^{m}xy^{m}z\in L$.

$a)$ Suppose for $L=\left \{ 0^{n}1^{n}0^{n}1^{n} \right \}$  $\left | wy \right |$ non-empty where $u=\epsilon$ and $z=\epsilon$ ,  $L=\left \{{\color{Red}{0^{n}} } 1^{n}0^{n}{\color{Red} {1^{n}}} \right \}$

then $\left | x \right |=1^{n}0^{n}$
But according to 3rd pumping lemma condition $\left | wxy \right |\leq n$


But it is not in the form $uw^{m}xy^{m}z\in L$, where loop exists for $w$ and for $y$ That is not possible for this language. So, it is non CFL.


$b)$ If we divide $L=uvxyz$ in $3$ segment, then atleast one segment doesnot in $v$ or in $y.$ Hence $xv^{2}xy^{2}z$ doesnot maintain a ratio of $1:2:3$. So, they cannot be pumped by pumping lemma.


$c)$  Let $L=a^{p}b^{p}$#$a^{p}b^{p}$

We show that string $L=uvxyz$ cannot be pumped using pumping lemma.

Say neither $v$ , nor $y$ contains #, otherwise $uv^{0}xy^{0}z$ not in $L$ 

If $v$ and $y$ are non-empty and occur in left hand side of #, then $uv^{2}xy^{2}z$ cannot be in $L.$ Because it is longer than left hand side of #.

Similarly , if $v$ and $y$ are non-empty and occur in right hand side of #, then $uv^{2}xy^{2}z$ cannot be in $L.$ Because it is longer than right hand side of #

Only, remaining case is when $v$ and $y$ are non-empty and straddle the #. but because the 3rd pumping lemma condition $\left | vxy \right |\leq p$

Hence $uv^{2}xy^{2}z$ contains more $0's$ on right hand side of #. So, it not in $L.$


$d)$ Now we can take $t_{1}=a^{p}b^{p}$,$t_{2}=a^{p}b^{p}$

So, $L=a^{p}b^{p}$#$a^{p}b^{p}$

Now proving is same as above.

 

edited by

Related questions

1 votes
1 votes
1 answer
3