edited by
1,192 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.3k
views
1 answers
1 votes
admin asked May 4, 2019
1,293 views
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ ... $B.$ What is the minimum value of $p$ that works in the pumping lemma$?$ Justify your answer$.$
579
views
0 answers
0 votes
admin asked May 4, 2019
579 views
Prove the following stronger form of the pumping lemma, where in both pieces $v$ and $y$ must be nonempty when the string $s$ is broken up$.$If $A$ is a context-free ... z\in A,$v\neq\epsilon$ and $y\neq\epsilon,$and$\mid vxy\mid\leq k.$
1.8k
views
1 answers
1 votes
admin asked May 4, 2019
1,828 views
Give an example of a language that is not context free but that acts like a $CFL$ in the pumping lemma$.$ Prove that your example works$.$ $\text{(See the analogous example for regular languages in Question 54.)}$
976
views
1 answers
0 votes
admin asked Apr 21, 2019
976 views
Describe the error in the following $ $proof$"$ that $0^{*}1^{*}$ is not a regular language. $($An error must exist because $0^{*}1^{*}$ is regular.$)$ ... cannot be pumped. Thus you have a contradiction. So $0^{*}1^{*}$ is not regular.