Read the informal definition of the finite state transducer given in Exercise 1.24. Give the state diagram of an FST with the following behavior. Its input and output alphabets are {0,1}. Its output string is identical to the input string on the even positions but inverted on the odd positions. For example, on input 0000111 it should output 1010010.

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₂.

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 T₁, the transition from q₁ to q₂ has input symbol 2 and output symbol 1. Some transitions may have multiple input–output pairs, such as the transition in T₁ from q₁ to itself. When an FST computes on an input string w, it takes the input symbols w₁ · · ·wn one by one and, starting at the start state, follows the transitions by matching the input labels with the sequence of symbols w₁ · · ·w_n = 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 q₁, q₂, q₂, q₂, q₂, q₁, q₁, q₁ and produces output 1111000. On input abbb, T₂ outputs 1011. Give the sequence of states entered and the output produced in each of the following parts.

a. T₁ on input 011

b. T₁ on input 211

c. T₁ on input 121

d. T₁ on input 0202

e. T₂ on input b

f. T₂ on input bbab

g. T₂ on input bbbbbb

h. T₂ on input ε

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