Solution Found!
A nite state transducer (FST) is a type of deterministic
Chapter , Problem 1.24(choose chapter or problem)
A nite state transducer (FST) is a type of deterministic nite automaton whose output is a string and not just accept or reject. The following are state diagrams of nite 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 inputoutput 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
Questions & Answers
QUESTION:
A nite state transducer (FST) is a type of deterministic nite automaton whose output is a string and not just accept or reject. The following are state diagrams of nite 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 inputoutput 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
ANSWER:Step 1 of 9
A finite state transducer (FST) is a deterministic finite automaton which gives an output of string. The transitions on FST have two symbols separated by slash. The left symbol designates the input and the right symbol designates the output.