Using pumping lemma to show a language is not context free(Complicated)

Question

How can i show that the following long language is not context free using the pumping lemma?

$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$

Such that:

$m,n,o \geq 1;$

$m>n>o>0;$

$i_1,i_2,...,i_{2m} \geq 0;$

$j_1,j_2,...,j_{2n} \geq 0;$

$k_1,k_2,...,k_o \geq 0$

And how can I conclude from that $L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$ is not a context free language?

I have been struggling with it for many hours, would really appreciate an explanation I can follow and learn from. The examples given in class are simpler and not on that level, and I don't know which z to take and how to break it in order to deduct in a proof that L is not context free.

Could you please give a slow explanation so I could learn fast?

My attempt for the first part:

Proving by negation that L is not a context free language: Assuming L is a context free language, then there should exist a pumping length P for which any string S such that $|S| \leq P$ can be divided into 5 pieces(uvxyz) while obeying the pumping lemma rules. Because of the information on the question, I'll focus on the first part of the lemma, i.e: $\forall i: uv^ixy^iz \in L$. The structure of a typical word from L will be:$S=abc^{p_1}bc^{p_2}...bc^{2p_i+2}def^{p_1}ef^{p_2}...ef^{2p_i}ghq^{p_1}...ghq^{2p_i-1}$. vxy cannot contain c,f,q's, We'll divide it into the following cases based on vxy. Don't know how to divide it or how to continue, would really appreciate your assistance with it. Very important to me

My attempt for the second part(I don't understand it well enough to solve the first part, I will ask for your help with it):

Proving by negation that L is not a context free language: Assuming L is a context free language, then there should exist a pumping length P for which any string S such that $|S| \leq P$ can be divided into 5 pieces(uvxyz) while obeying the pumping lemma rules. Because of the information on the question, I'll focus on the first part of the lemma, i.e: $\forall i: uv^ixy^iz \in L$. The structure of a typical word from L will be:$S=0^p1^p2^p$. vxy cannot contain a,b,c's, We'll divide it into the following cases based on vxy:

1. Doesn't contain 0: pumping S with 0 to obtain $uv^0xy^0z=uxz$. in this case, there are fewer 1 or 2, so not in L.
2. There's 0 but not 2: pumping S with 2 to obtain $uv^2xy^2z$, meaning more 0's than 2's, so it is not in L.
3. There are no 2's: pumping S with 2 to obtain $uv^2xy^2z$, meaning more 1's or 0's than 2's, so it is not in L.

Since each option was checked and each one contradicted, It can be safe to assume that $L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$ is not a context free language since it does not adhere to the pumping lemma.

Thank you very much

Answer 1

Start with a long enough string $w$ in $L$ in which $m=p+2,n=p+1,o=p$ and

• $i_1,...,i_{2m}=0$
• $j_1,...,j_{2n}=0$
• $k_1,...,k_{o}=0$

$w = a\; b^{2(p+2)}\; d\; e^{2(p+1)}\; g\; h^{p} $

Then apply pumping lemma (it should be easier ;-).

If you want to "reduce" $L$ to $L' = \left\{0^i1^j2^k|1\le \:i<j<k\right\}$ then you must use closure properties, in particular CFLs are:

1. closed under homomorphism
2. closed under reverse homomorphism
3. closed under reversal

The homomorphism that you can use is: $H(a) = H(c) = H(d) = H(f) = H(g) = H(q) = \epsilon, H(b) = \bar{2}, H(e) = \bar{1}, H(h) = \bar{0}$

Applying $H$ to the language gives $H(L) = \{ \bar{2}^{2m} \bar{1}^{2n} \bar{0}^{o} \mid m > n > o > 0\}$

Then you can use a reverse homomorphism $\varphi(2)=\bar{2}\bar{2}, \varphi(1)=\bar{1}\bar{1}, \varphi(0) = \bar{0}$ and you get:

$\varphi^{-1}( H(L)) = \{ 2^m 1^n 0^o \mid m>n>o>0 \}$

and finally apply closure under reversal:

$(\varphi^{-1}( H(L)))^R = \{ 0^o 1^n 2^m \mid 0<o<n<m \} = L'$

If $L$ is CF then by closure properties $(\varphi^{-1}( h(L)))^R = L'$ should be CF, which is not the case.

Answer 2

Let us check the first part, $L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$ where $m>n>o>0$, $i_1,i_2,...,i_{2m} \geq 0$, $j_1,j_2,...,j_{2n} \geq 0$, $k_1,k_2,...,k_o \geq 0$. Note the "where" clause means $\#_b(w)$ and $\#_e(w)$ are even and $\#_b(w)>\#_e(w)>2\#_h(w)$.

Assume $L$ is context-free for the sake of contradiction. Then there is a $p\ge1$, the pumping length such that every word in $L$ of length no less than $p$ can be written as $uvxyz$ such that $|vxy| \le p$, $|vy| \ge 1$ and $uv^kxy^kz$ is also a word in $L$ for all nonnegative number $k$.

Consider $w=a{\underbrace{bb\cdots b}_{2(p+2)\text{ times}}}$$d\underbrace{ee\dots e}_{2(p+1)\text{ times}}$$g\underbrace{hh\cdots h}_{p\text{ times}}$, a word that is in $L$ but "almost not in $L$".

Decompose $w=uvxyz$ where $v$ and $y$ together is the pumpable part of the word. There are following cases of the pumpable part.

• The pumpable part contains $a$, $d$, or $g$.

  One of the them will disappear if we pump down by letting $k=0$, i.e., $uv^0xy^0z=uxz$.

• Otherwise, the pumpable part must contain at least one of $b,e,h$.

  • the pumpable part does not contains $h$. So it must contain either $b$ or $e$.

    Pumping down by letting $k=0$ will decrease either $\#_b(w)$ or $\#_e(w)$ without changing $\#_h(w)$.

  • Otherwise, the pumpable part contains $h$. Since $vxy$ is too short to contain both $b$ and $h$, the pumpable part cannot contain $b$.

    Pumping up by letting $k=2$ will increase $\#_h(w)$ without changing $\#_b(w)$.

In all cases, $uvxyz$ can be pumped into a word not in $L$. So $L$ does not behave as described by the pumping lemma, which invalidate our assumption that $L$ is context free.

---

Exercise. Show that $\left\{w\in \{a,b,c\}^*\mid \#_a(w)> \#_b(w)\text{ and }\#_a(w)> \#_c(w) \right\}$ is not a context-free language.