Skip to main content

Section Finite State Transducers

Suppose the directions on a vending machine ask the user to:

  1. Choose either (P) Peanuts (65¢) or (D) Doritos (45¢).

  2. Insert only enough quarters or half dollars to pay for your choice.

  3. Press “RETURN”.

In order to execute instructions, the machine must remember, at any time, the user's selection and the amount of money it has received. Memory will take the form of internal states, one for each possible data set. The machine logic is represented by the directed labeled graph in Figure 9.4. The circles are the internal states that form the vertices of the graph. The arrows tell

  1. what the output should be for each input and

  2. to what new internal state the machine should go.

Unspecified inputs leave the state unchanged and give no output.

Figure 9.4. Finite State Transducer for the Peanut/Dorito Machine \(M_1\)

The start state is “s”, and each other state has a name that indicates what it is to remember. The symbol “–” means no output.

Problem 9.5.

Suppose our vending machine in Figure 9.4 is in state “s.” Describe what happens when a user inputs the sequence,“PqqhR”. What should happen if the user inputs “DhqqqRh”?

In order to describe these kinds of machines in general, we need several definitions.

Definition 9.6.

An alphabet is a finite set \(\Sigma\) of symbols. Given an alphabet \(\Sigma\) a string is a finite sequence of symbols from \(\Sigma\text{.}\) We denote by \(\Sigma^*\) the set of all strings of symbols from \(\Sigma\text{.}\) An alphabet \(\Sigma\) includes the empty string denoted by \(\lambda\text{.}\) The length of the non-empty string \(w = a_1 a_2 \dots a_n \in \Sigma^*\) is \(n\) and is denoted by \(|w|=n\text{.}\) The length of the empty string is \(|\lambda|=0\text{.}\)

For example, Figure 9.4 has \(\Sigma_1 := \{P, D, q, h, R\}\) as its input alphabet and \(\Sigma_2 := \{P, D, +, 0, 1, 3, 5\}\) as its output alphabet.

Definition 9.7.

A finite state transducer (abbreviated \(FST\)) is a quintuple \(\dsp M = \langle \Sigma_1, Q, \Sigma_2, s, \delta\rangle\) where

  1. \(\Sigma_1\) is a finite set of symbols, called the input alphabet of \(M\text{,}\)

  2. \(Q\) is a finite set, called the internal states of \(M\text{,}\)

  3. \(\Sigma_2\) is a finite set of symbols, called the output alphabet of \(M\text{,}\)

  4. \(s\in Q\) is called the initial state of \(M\text{,}\) and

  5. \(\delta: Q\times\Sigma_1 \to Q\times\Sigma^*_2\) is called the state transition function of \(M\text{.}\)

A finite state transducer is illustrated with a transition diagram such as the one in Figure 9.4. A transition diagram is a labeled directed graph whose vertices are the states of \(Q\text{,}\) and we label the arrow from state \(q\) to state \(q'\) with \(a/w\) if \(\delta(q,a) = (q',w)\text{.}\) That is, in state \(q\in Q\) reading input symbol \(a\in \Sigma_1\) the machine is to go to state \(q'\in Q\) and output symbol \(w\in \Sigma^*_2\text{.}\) When the machine gives no output, we have expressed this by writing “\(a/-\)”. Technically this means that the output is the empty string \(\lambda\) so it could also be written as “\(a/\lambda\)”.

Figure 9.8. A Transition Diagram
Problem 9.9.

Construct a transition diagram for a FST to control a stamp vending machine that asks the user to

  1. choose either a 10 stamp book \((\)$3.40\()\) or a 20 stamp book \((\)$6.80\()\text{;}\)

  2. insert either $1, $5 or $10 bills, larger bills before smaller bills;

  3. press “RETURN” for stamps and change.

Problem 9.10.

Construct a transition diagram for a finite state transducer that will read a string of letters from the set \(\{a,b,c\}\) starting from the left \((\)for example “caabbacccbacb”\()\text{.}\) As output, it will change each letter to an “e” until it has read three “a”s. After that, it will change each “a” to “b” each “b” to “c” and each “c” to “a” \((\)for example, “eeeeeeaaacbac”\()\text{.}\)

Problem 9.11.

Construct a transition diagram for a finite state transducer which will take as input a finite string of letters from \(\{a,b,c,x\}\) \((\)for example, “abacaaccabxbxacxxc”\()\text{.}\) It will output the letter “q” for each input of \(a, b\) or \(c\) until it reads an “x”. It will then divide the number of “a”s it has read by 3, return the remainder as its last output, and go back to the start state. \((\)In the above example, the output would be “qqqqqqqqqq2”.\()\)

We can think of the input to a FST as a question and the output as the answer. For example, suppose we would like to get both a bag of peanuts (P) and a bag of Doritos (D) from the vending machine for Figure 9.4. We could input PhhqDR to the FST to see what the vending machine would do. The FST will answer with the output P+35. This means that the vending machine would return a bag of peanuts and 35 cents change, keeping the extra 25 cents and ignoring the request for Doritos. We might then read the instructions more carefully and do this as two separate transactions.