What is the expressive power of finite-state transducers and pushdown transducers?

One would assume that a finite state transducer can perform any translation such that the resulting string is from a regular grammar. Similarly, that a pushdown transducer can generate strings from CFG grammars.

I am, however, unsure about this because we can construct a finite state transducer which translates a string of the form $ab$ to $\{ a^n b^n : n \ge 1 \}$, which is irregular.

Is this the case? If so, can anyone provide the relevant literature?

• Can you specify such a transducer? I believe it will conver $ab$ to $a^kb^k$ with a specific fixed $k\ge0$, but not to the set $\{a^kb^k \mid k\ge 0\}$, right? So this is just a single word. A single word is a finite language, which means it is regular. – Ran G. May 19 '16 at 17:18

we can construct a finite state transducer [that maps $\{ab\}$ to $\{a^nb^n n \geq 1\}$].

No, we can't. REG is closed against finite-state transduction.

Wikipedia hints as much without citation; planetmath.org lists some standard references, in particular Hopcroft/Ullman.

Any string is from (the language of) a regular grammar since the language of all words is regular. Regular and context-free only make sense when you talk about entire languages.

If you take as input always the language of all words, then indeed the output will always be regular for finite state transducers and cf for pushdown transducers.

If your input can be arbitrary languages L and you just take the set

{v:(u,v) is in the transduction for u\in L}


then you can obtain arbitrarily complex languages by inputting them and just performing the identity transduction.