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.

  • $\begingroup$ L -> AC A -> aAbb | ϵ C -> cC | ϵ $\endgroup$ – Matthew Mar 20 '18 at 0:36
  • $\begingroup$ Does that seem right? :) $\endgroup$ – Matthew Mar 20 '18 at 0:36
  • $\begingroup$ @Matthew: You now have to prove that it generates the correct language, so you should acquire more confidence as you do the proof :) $\endgroup$ – rici Mar 20 '18 at 0:47
  • $\begingroup$ I thought that since we can show that it has a CFG, then it is a context free language. What do you suggest doing? $\endgroup$ – Matthew Mar 20 '18 at 0:49
  • 1
    $\begingroup$ @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. $\endgroup$ – rici Mar 20 '18 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.