# Does a pushdown automata exists for the following language?

I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another alphabetical comparison to the above language as

1. $L_1= a^n b^n c^{2n} d^n$

2. $L_2= a^n b^{2n} c^n d^{2n}$

And a mixture of above will lead to cfg. Because now we have two comparison so not only we can push the symbol but with the help of other symbol we can pop it so as to empty the stack implies to acceptance of the strings.

3. my question is I do not know that whether my assertion to the modification of the language is right or wrong so please if you can tell me where iam wrong or right it would be helpful.

4. One more thing if iam right, then please show the cfg production to derive them as I can make PDA for them( if iam right) but finding hard to assign production the accepts the above cgl language ( if its then) Thanks
• I'd suggest you fix the grammar in your question - as it stands, it's a bit difficult to understand what you are trying to ask. Aug 29, 2018 at 3:46
• I did not get you, like iam asking that the modification of non cfl = ( a^n b^n c^n) to (a^n b^n c^n d^n) will make the later a cfl or not Aug 29, 2018 at 4:19
• Your new languages are also not context-free. You can prove it using the pumping lemma. Aug 29, 2018 at 4:30
• See our reference question for detailed explanations on how to prove that your language is not context-free.
– Raphael
Aug 29, 2018 at 11:49
• Also, what exactly do you mean by "mixture"?
– Raphael
Aug 29, 2018 at 11:49

A string homomorphism is a function $f\colon \Sigma \to \Sigma^*$ that replaces each character in a string with a (possibly empty) string over the same alphabet. For a string $w=w_1\dots w_\ell$, we define $f(w)= f(w_1)\cdots f(w_\ell)$. Context-free languages are closed under string homomorphisms. That is, if a language $X$ is context free, so is the language $\{f(w)\mid w\in X\}$ for any string homomorphism $f$.
So, suppose that either of your languages were context-free, and consider the homomorphism defined by $f(a)=a$, $f(b)=b$, $f(c)=c$, $f(d)=\varepsilon$. We have $f(L_1)=\{a^nb^nc^{2n}\mid n\geq 0\}$ and $f(L_2) = \{a^nb^{2n}c^n\mid n\geq 0\}$. Neither of these is context free, which contradicts the assumption that $L_1$ and $L_2$ are context-free.