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

DEFINITION 1.5:

A finite automaton is a 5-tuple (Q, Σ, δ, q₀, F), where

1. Q is a finite set called the states, 2. Σ is a finite set called the alphabet, 3. δ : Q × Σ⇾Q is the transition function,4. q₀ ∈ Q is the start state, and 5. F ⊆ Q is the set of accept states.

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