# Of which Chomsky-type is the language $L = \{a^jb^ic^{2i} | i,j \in \mathbb{N}^0\}$?

At first I thought the language would be context sensitive because it seems that it can be shown with the pumping lemma for regular languages, that it's not a regular language and analogously with the pumping lemma for context free languages, that it is not context free. But it upon further pondering I came up with a pushdown automaton that would match this language. So I'm a bit at loss as to what type of language it is. I hope someone can help.

• I'm not sure what you mean by "it seems that it can be shown". Do you mean that you have written down what you believe to be a proof, or just that you feel that a proof should exist. If the latter, I suggest you try to write down the proofs and see where that gets you. As I'm sure you know, if there's a PDA for the langauge, it's context-free so either your automaton is wrong, your context-free pumping lemma proof is wrong or your suspicion that there exists such a proof is wrong. If all you have is a suspicion, you should definitely try to produce an actual proof. Commented May 23, 2016 at 20:02

The language is context-free. You can use the pumping lemma for regular languages to show that it is not regular. However, you can construct a context-free grammar to show that the language is context free. For example, the following CFG grammar would generate it

$S \to A\ |\ aS$

$A \to \epsilon\ |b A cc$

• ... and then prove it correct. Commented May 23, 2016 at 22:21

If the language required twice as many c's as a's, the equivalent grammar should look like

S -> aScc | bB | epsilon

B -> bB | epsilon

• (Have another look at the specification of $L$?) Commented Mar 31, 2023 at 8:11