PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$

Question

On my compilation theory exam we had the following problem:

Construct a PDA translator (just one stack) such that it translates the language $$ a^{m+n}b^n \rightarrow x^{2m+2}y^{3n}, \text{ where } n,m \geq 0$$
I cant think of any solution. My approach was as follows: I would put in the stack $m+n$ symbols of $a$. Then, for every $b$ in $b^n$ I would remove one $a$. Then I would be left with $m$ symbols of $a$ in the stack. After, that, I would emit two symbols of $x$ and I would empty the stack. For every $a$ that was left I would emit two symbols of $x$. I could not figure out how to obtain the second part because in order to determine $m$ I would need subtract the $n$ from $b^n$.

By PDA translator I mean a regular PDA but instead of accepting/rejecting a language, we use it to transform a language into another (every transition in the automaton can emit some symbols).

Answer 1

This seems impossible if the translator has to be deterministic.

Let's clean up the problem and ask the PDA to convert $a^{n+m} b^n$ to $x^m y^n$ (your translator can be converted to such a translator by using a regular transducer). Since your PDA is deterministic, it cannot output anything until it knows whether $m = 0$ or not, which can happen in one of two ways: either it reaches the end of input, or it reads $a^n b^n$ (which must also be the end of input).

Now let us modify your PDA so that instead of outputting $x^m y^n$, it checks that the rest of the input has the form $x^m y^n$. We obtain a deterministic PDA accepting the language of all words of the form $a^{n+m} b^n x^m y^n$, yet this language is not context-free (you can see this by intersecting with $a^*b^*y^*$ to get the language of all words of the form $a^nb^ny^n$).