$L = \{ a^jb^mc^m : 0 \le j \le m \}$ prove that it is context free.

Question

Having the following language:

$$L = \{ a^jb^mc^m : 0 \le j \le m \}$$ I have to prove that it is context free.

I have tried to consider the concatenation of smaller context free languages, to take advantage of the fact that the concatenation of context free languages, still results in a context free language, but, I can't, because the quantity of $a$ is dependent from $b,c$, I can't separate that languages.

So, another way, I have tried to construct a context free grammar, but, without success, because, I have obtained that the $a$ can be produced without restrictions:

$$ \begin{array}{lcl} G & = & (X,V,S,P) \\ X & = & \{ a,b,c \} \\ P & = & \left \{ \begin{array}{lcl} S & \rightarrow & \underset{(1)}{\lambda} & \Biggm | & \underset{(2)}{aA} \\ A & \rightarrow & \underset{(3)}{aA} & \Biggm | & \underset{(4)}{B} \\ B & \rightarrow & \underset{(5)}{bBc} & \Biggm | & \underset{(6)}{\lambda} \\ \end{array} \right \} \end{array}$$ Please, can you help me? How can I contruct a proper grammar for that language?

Thanks! (:

---

In ADDITION:

to find a proper CF grammar, proves only that the language is at least CF, so, it is not the proper way to proceed.

I have followed the advice of the user @posilon.

I post only a particular case, where I don't encounter any contraddiction, because writing the entire exercise it is too long. In the result I obtained, I can declare that the language IS context free.

In the case when $v$ contains all of $a$ and $x$ contains all of $b$, where :

$$vwx = a^kb^l, \quad 2 \le k+l \le p$$

$$\begin{array}{lcl} v & = & a^{k_1}b^{l_1}\\ x & = & a^{k_2}b^{l_2} \end{array}$$

considering the pumped string :

$$uv^2wx^2y = a^{p+k_1+k_2}b^{p + l_1 + l_2}c^p$$

I obtain:

$$\begin{array}{lcl} uv^2wx^2y & = & a^{p+k_1+k_2}b^{p + l_1 + l_2}c^p \\ & = & a^{p+k+0}b^{p + 0 + l}c^p \\ & = & a^{p+k}b^{p+l}c^p \end{array}$$

check if the initial condition is still valid:

$$\begin{array}{lcl} 0 & \le & p+k & \le & p+l \\ - p & \le & k & \le & l \end{array}$$

it's TRUE, $k \ge 1, l \ge 1$. So $L$ is CF. What do you think? Thanks again (:.

Answer 1

You can use Ogden's lemma to show that $L$ is not context free.

Proof sketch:

Using the notation of the Wikipedia article, let $s=a^pb^pc^p \in L$ and mark every $a$. Suppose that $L$ is context free. By Ogden's lemma, we can write $s=uvwxy$ so that $vx$ has contains at least one marked symbol and $uv^nwx^ny\in L$ for all $n \geq 0$. The latter implies that $v=b^i$ and $x=c^i$ for some $i$, since the length of $vx$ is at least $1$. This is a contradiction since then $vx$ fails to have any marked positions.