Read the informal definition of the finite state transducer given in Exercise 1.24. Give the state diagram

Question:

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 T1 and T2.

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


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 ε

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question
Question Posted: