1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ L -> AC A -> aAbb | ϵ C -> cC | ϵ $\endgroup$
    – Matthew
    Commented Mar 20, 2018 at 0:36
  • $\begingroup$ Does that seem right? :) $\endgroup$
    – Matthew
    Commented Mar 20, 2018 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
    Commented Mar 20, 2018 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
    Commented Mar 20, 2018 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
    Commented Mar 20, 2018 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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