Question

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 (page 35). Assume that an FST has an input alphabet $\sum$and an output alphabet but not a set of accept states. Include a formal definition of the computation of an FST.

(Hint: An FST is a 5-tuple. Its transition function is of the form$\delta :Qx\sum \to QxT$

Short answer

The transition is $\delta (qi+1\text{'},wi+1)=(qi+1\text{'},xi+1)for0⩽i <n$

Step-by-step solution

Introduction

Finite State Transducer:

• A deterministic finite transducer is indeed a deterministic finite state automata that includes either an inputs as well as an output sequence..

• It turns every input file to something like a string output..

Explanation

The following seems to be the precise definition of a State Machine Transducer (FST):

A Finite State Transducer (FST) is a 6-tuple machine with the following representation:$M=\left(Q,\sum ,r,\delta ,q_0\right)$where

• Q is a finite set of states.

• $\sum$ is a finite set of input alphabets.

• r is a finite set of output alphabets.

• $\delta :Qx\sum \to QxT$is the transition function that defines rules.

• $q_0\in Q$, is the start state.

The proper definition for Finite State Transducer (FST) computing seems to be as follows:

•This finite state machine gets computed by converting the input stream into an output string.

• Suppose w is really a string that spans the source alphabet. $\sum$where x is very much an output string made out of the letters of the alphabet r .

• This changeover takes place in a series of states. $q_0,q_1,q_2,...q_{n}inQ$ such that $q_0=q_0$