Question

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

Answer 1

An FST with the specified behavior can be represented by the following state diagram. The states are labeled as even or odd based on the position of the input symbol. Transitions are determined by the input symbols, and the output is identical to the input on even positions but inverted on odd positions.

Step-by-step explanation:

To construct the FST, create two sets of states: one for even positions and one for odd positions. For each set of states, transitions are defined for input symbols {0, 1}. In the even state set, transitions lead to the same state for both 0 and 1, ensuring the output is identical to the input. In the odd state set, transitions invert the output on odd positions. The FST starts in the even state, and transitions between even and odd states occur based on the position in the input string.

This behavior is achieved by defining transitions such that the output at even positions mirrors the input, while at odd positions, the output is inverted.

For example, on input 0000111, the FST transitions as follows: (even state) 0 -> (odd state) 1 -> (even state) 0 -> (odd state) 1 -> (even state) 0 -> (odd state) 0 -> (even state) 1. The output is then 1010010, satisfying the specified behavior.