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!
Asked By : KrasivaM
Answered By : babou
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}$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42281
0 comments:
Post a Comment
Let us know your responses and feedback