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

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

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


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.