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

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).

• Is your PDA translator allowed to be nondeterministic? – Hendrik Jan May 13 at 19:55
• @HendrikJan no, it wasn't allowed. – Daniel Matei May 13 at 20:03

## 1 Answer

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$$).