2
$\begingroup$

In one of my exams I needed to find a CFG for $L=\{a^ib^{2i}c^{2i} | i>1\}$.

however, it really seemed to me that it is not a CFG. I tried to show it is not using the pumping lemma, and think I managed, but I don't really know if I did something wrong there.

So was I wrong or the question is wrong?

Thank you.

$\endgroup$
2
$\begingroup$

Your language is not context-free. You can see this by applying the inverse of the homomorphism which sends $a$ to $a$, $b$ to $bb$ and $c$ to $cc$; this results in the language $\{a^ib^ic^i : i > 1\}$, which differs from a well-known non-context-free language by just a finite number of words.

$\endgroup$

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.