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

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

• 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.

• 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

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

• closed under reverse homomorphism

• 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.

StackExchange Computer Science Q#111232, answer score: 3