# PushDown automata for a^(n) b^(2n) c^(2n) d^(n)

i got this question in a theory of computation quiz "give pda for a^(n) b^(2n) c^(2n) d^(n)"

i am arguing that there is no pda for that question but our ta says that we can push 5x to the stack then pop x each time we read a b or c or d. i am arguing that doesn't guarantee count because we might get only "d"s which one of us is right

• Neither of your arguments are really sound. If you want to prove that the language is not context-free, you should try with the pumping lemma. Jan 3 at 12:43

You are right that the suggestion of the TA does not work. Using that approach one will accept $$\{\; a^n b^i c^k d^\ell \mid 5n = i+j+\ell \;\}$$. We can force the PDA to make $$i$$ and $$j$$ even, but that will not help much.
Of course this does not prove that there is no PDA for the language $$K = \{\;a^nb^{2n}c^{2n}d^n \mid n\ge 1\;\}$$ : another clever technique might work.
Recall that $$L = \{\;a^nb^nc^n\mid n\ge 1\;\}$$ is a very similar language, known not te be context-free. Hence it is intuitively clear that also your language is not context-free.
To formally show that one might use the direct approach and use the pumping lemma for CF languages to show it is not context-free. Alternatively one may use closure properties of the context-free languages to show that if $$K$$ is context-free then so is $$L$$ (leading to a contradiction). Informally the language operations you need would be halving the number of $$b$$'s and $$c$$'s and deleting the $$d$$'s. Formally those can be "implemented" by homomorphisms and their inverses. Those operations map letters to words.