World's most popular travel blog for travel bloggers.

[Solved]: How to create this pushdown transducer? (formal languages and automata)

, , No Comments
Problem Detail: 

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback