Read the informal definition of the finite state transducer given in Exercise 1.24. Prove that no FST can output w^R for every input w if the input and output alphabets are {0,1}.

Exercise 1.24.

A finite state transducer (FST) is a type of deterministic finite automaton whose output is a string and not just accept or reject . The following are state diagrams of finite state transducers T₁ and T₂.

Transcribed Image Text:

a/1 0/0 1/0 1/1 2/1 a/0 b/1 2/1 92 93 b/1 92 0/0 a/1 T1 T2