0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Jan 3, 2023 at 12:43

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.