Create a pushdown transducer that translates $a^m b^{2m}c^{m+n}$ into $b^{n-m}$, with $n\geq m \geq 0$. How should I use the stack to remember or to compute how many characters of c to read? And how can I output $b^{n-m}$?

I have also tried to simplify the problem and firstly create a pushdown automata for $a^m b^{2m}c^m$, but I didn't succeed.

Thank you!


It is no surprise you could not create that PDA: the language $\{a^m b^{2m}c^m\mid m\geq 0\}$ is not CF. The same is true of $\{a^m b^{2m}c^{m+n}\mid n\geq m\geq 0\}$. You may try to prove it.

Hence, I suspect that the pushdown transducer is not supposed to recognize the input string but assumes it is well formed, and simply has to translate correctly when it is.

So I would simply use the pushdown stack of the transducer to collect the information to be found in the input (supposed to be well formed) to produce the correct output, without worrying about acceptance. You do not care what happens when the input string is not well formed. It is actually quite simple to produce $b^{n-m}$


Your Answer

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

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