Read the informal definition of the finite state transducer given in Exercise 1.24. Give a formal definition of this model, following the pattern in Definition 1.5 (page 35). Assume that an FST has an input alphabet and an output alphabet Σ but not a set of accept states. Include a formal definition of the computation of an FST.An FST is a 5-tuple. Its transition function is of the form δ: Q× Σ → Q×Γ.)
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 T1 and T2.
Each transition of an FST is labeled with two symbols, one designating the input symbol for that transition and the other designating the output symbol. The two symbols are written with a slash, /, separating them. In T1, the transition from q1 to q2 has input symbol 2 and output symbol 1. Some transitions may have multiple input–output pairs, such as the transition in T1 from q1 to itself. When an FST computes on an input string w, it takes the input symbols w1 · · ·wn one by one and, starting at the start state, follows the transitions by matching the input labels with the sequence of symbols w1 · · ·wn = w. Every time it goes along a transition, it outputs the corresponding output symbol. For example, on input 2212011, machine T1 enters the sequence of states q1, q2, q2, q2, q2, q1, q1, q1 and produces output 1111000. On input abbb, T2 outputs 1011. Give the sequence of states entered and the output produced in each of the following parts.
a. T1 on input 011
b. T1 on input 211
c. T1 on input 121
d. T1 on input 0202
e. T2 on input b
f. T2 on input bbab
g. T2 on input bbbbbb
h. T2 on input ε
