The PDA has to recognize the language $L = \{w\in \{a,b,c\}^* \mid |w|_a = |w|_b$ or $ |w|_a=|w|_b\}$.
Currently I have an automaton which recognises that language if $|w_a|=|w|_b$ xor $|w_a|=|w|_c$. It looks like this:PDA

It is xor because it is going to empty the stack before it could check next letter's occurence.
My question is how can I divide this into two PDAs (one recognises $|w|_a=|w|_b$ and the other one recognises $|w|_a=|w|_c$) and take the union of those PDAs?
Or is there any better solution?

  • $\begingroup$ Do you actually need to produce a PDA? If not, producing a PDA for $\#a=\#b$ is enough, since $\#a=\#c$ is essentially identical and context-free languages are closed under taking unions. Alternatively, nondeterminism is your friend. $\endgroup$ – David Richerby Apr 30 '17 at 20:26
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael May 1 '17 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.