Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
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.
