# Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free

Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free.

I have a grammar like this but there are some strings that are not be able to be generated

\begin{align} S &\to aSbb \;|\; C \\ C &\to cC \;|\; \epsilon \end{align}

One example is the string $abbc$ cannot be generated.

You've almost got it. Consider that $L_1$ is simply the concatenation of $L_a$ and $L_c$, where $L_a = \{a^ib^{2i} \;|\; i ≥ 0\}$ and $L_c = \{c^j \;|\; j ≥ 0\}$, since the two parts of each sentence are independent of each other.

That should suggest a grammar which starts with the production $L\to AC$, and which then proceeds to define $A$ and $C$ in the obvious way.

• L -> AC A -> aAbb | ϵ C -> cC | ϵ Commented Mar 20, 2018 at 0:36
• Does that seem right? :) Commented Mar 20, 2018 at 0:36
• @Matthew: You now have to prove that it generates the correct language, so you should acquire more confidence as you do the proof :)
– rici
Commented Mar 20, 2018 at 0:47
• I thought that since we can show that it has a CFG, then it is a context free language. What do you suggest doing? Commented Mar 20, 2018 at 0:49
• @Matthew: Yes. You have to show that any string in the language has a derivation from the grammar, and that every string derived from the grammar is in the language. (That is, two separate proofs.) Showing the derivation is trivial, and the other way is almost as simple. Once you've done that, you no longer have to ask "Does that look right?" because you know that it is :) If in doubt, ask your professor or TA.
– rici
Commented Mar 20, 2018 at 0:58