Finite-state transducers

A coffee vending machine has a slot for receiving coins, a button whose press, after a sufficient amount has been paid, dispenses coffee, and a receptacle through which it gives the customer change. The machine accepts coins of denominations 1, 2, and 5 rubles. A cup of coffee costs 8 rubles. While the amount received is insufficient, a red light is on. If the amount received by the machine becomes greater than or equal to 8 rubles, a green light turns on, and after the button is pressed the machine pours the coffee and, if necessary, dispenses change using the smallest number of coins. If the machine receives a coin while the green light is on, it immediately returns it.

Construct a finite transducer that models the operation of this machine. Determine the input and output alphabets and construct its program.

An electronic clock has a display showing hours, minutes, and seconds, as well as two control buttons. The first button switches the clock from normal mode to time-setting mode — first to setting the hours, then the minutes, then the seconds, and then returns it to normal mode. The second button does nothing in normal mode, while in setting mode pressing it increases by one the number of the hours, minutes, or seconds being set, respectively.

Construct a finite transducer that models the operation of the clock. On input it receives press signals from the two buttons, and on output it produces signals for changing the mode and for incrementing the corresponding number. Draw the diagram of the transducer.

Construct a finite transducer that multiplies a number written in binary by 3. The digits in the binary representation of numbers go from least significant to most significant, that is, the number ten looks like this: 0101.

Construct a finite transducer that computes the integer division by 3 of a number written in decimal. The digits are written in decreasing order of place value (in the "usual" order).

Prove Proposition 93 on p. 286.

Proposition 93: For a finite transducer $\mathfrak {M}$, its configuration $\sigma$, and a natural number $k$, there exists at most one configuration $\tau$ such that $\sigma \vdash_{\mathfrak {M}}^{k} \tau$.

Construct finite transducers that perform the decoding from Problem 269.

A finite transducer $\mathfrak {M}=\left(Q, \Sigma , \Omega , P_{1}, q_{0}\right)$ is defined as follows: $Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}\right\} , \Sigma =\left\{ 0,1\right\} , \Omega =\left\{ A, P, T\right\}$, and the program $P_{1}$ is given by the table in Fig. 23.

A finite transducer $\mathfrak {M}_{c}=\left(Q, \Sigma , \Omega , P_{2}, q_{0}\right)$ is defined as follows: $Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}\right\} , \Sigma =\left\{ 0,1\right\} , \Omega =\left\{ 0,1\right\}$, and the program $P_{2}$ is given by the table in Fig. 23. This transducer subtracts some constant $c$ from the input number $x$ written in binary, that is, when $c \leqslant x$ it outputs the number $y=x-c$ in binary. What is this constant $c$? The digits in the binary representation of the numbers go from least to most significant, that is, the number ten looks like this: 0101.

A change-making machine has a slot for inserting coins and a hopper for dispensing them. The machine accepts coins of denominations 1, 2, and 10 rubles and makes change in 5-ruble coins. The display shows the amount already inserted, and as soon as the amount becomes sufficient, the machine immediately dispenses the required number of 5-ruble coins.

Construct a finite transducer modeling the operation of this machine. Determine the input and output alphabets and construct its program.

A coffee vending machine has a slot for receiving coins, a button whose press, once a sufficient amount has been paid, dispenses the coffee, and a hopper through which it dispenses change to the buyer. The machine accepts coins of denominations 1, 2, and 5 rubles. A cup of coffee costs 8 rubles. While the amount received is insufficient, a red light is on. If the amount received by the machine becomes greater than or equal to 8 rubles, then a green light turns on, and after the button is pressed the machine pours the coffee and, if needed, dispenses change using the smallest number of coins. If the machine receives a coin while the green light is on, it immediately returns it.

Construct a finite transducer modeling the operation of this machine. Determine the input and output alphabets and construct its program.

An electronic clock has a display showing hours, minutes, and seconds, along with two control buttons. The first button switches the clock from normal mode into time-setting mode — first into hour-setting, then minute-setting, then second-setting, and then returns it to normal mode. The second button does nothing in normal mode, while in setting mode pressing it increments by one the number of hours, minutes, or seconds currently being set, respectively.

Construct a finite transducer that models the operation of the clock. Its input consists of signals from presses of the two buttons, and its output consists of signals for changing the mode and incrementing the corresponding number. Draw the diagram of the transducer.

Fig. 24: Automaton programs from Problems 439, 440, and 441.

Construct a finite transducer that multiplies a number in binary notation by 3. The digits are written in order of increasing place value (as in Problem 432 on p. 129).

Construct a finite transducer that performs integer division of a number in decimal notation by 3. The digits are written in order of decreasing place value (in the "usual" order).

Show that if the homomorphism $C: \Sigma^{*} \rightarrow \Omega^{*}$ is prefix-free, then the result of the inverse encoding $C^{-1}$ can be computed by a finite transducer. We assume $C^{-1}(w)$ may be anything if $w \notin \operatorname {rng} C$.

Construct finite transducers performing the decoding from Problem 503: using the Huffman method, construct optimal binary encodings for the words

Prove an analogue of the pumping lemma for finite transducers. Let $f: \Sigma^{*} \rightarrow \Omega^{*}$ be a function computed by some finite transducer $\mathfrak {M}$. Then there exist constants $n$ and $m$ such that for any word $w \in \Sigma^{*}$ and any fragment $u$ of it of length $n$ or more: $w=\alpha u \beta ,\left|u\right| \geqslant n$, the following holds. There is a splitting $u=x y z, 1 \leqslant \left|y\right| \leqslant n$, and a splitting $f(w)=X Y Z \in \Omega^{*}$ such that $f\left(\alpha x y^{i} z \beta \right)=X Y^{i} Z$ for all natural $i$, $\left|X\right| \leqslant m\left|\alpha x\right|$, $\left|Y\right| \leqslant m\left|y\right|$, and $\left|Z\right| \leqslant m\left|z \beta \right|$. $\circledast$

Using Problem 534, show that there is no finite transducer that would translate a number from unary notation to binary or vice versa (see Section 24). $\circledast$

Using Problem 534, show that there is no finite transducer that performs "reversal" of a word over the alphabet $\left\{ a, b\right\}$. $\circledast$

Find an unambiguous homomorphism $C: \Sigma^{*} \rightarrow \Omega^{*}$ that is computed by some finite transducer, but for which the inverse encoding $C^{-1}$ cannot be performed by any finite transducer. We assume $C^{-1}(w)$ may be anything if $w \notin \operatorname {rng} C$. $\circledast$

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_{1}$ and $T_{2}$.

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_{1}$, the transition from $q_{1}$ to $q_{2}$ has input symbol 2 and output symbol 1. Some transitions may have multiple input-output pairs, such as the transition in $T_{1}$ from $q_{1}$ to itself. When an FST computes on an input string $w$, it takes the input symbols $w_{1} \cdots w_{n}$ one by one and, starting at the start state, follows the transitions by matching the input labels with the sequence of symbols $w_{1} \cdots w_{n}=w$. Every time it goes along a transition, it outputs the corresponding output symbol. For example, on input 2212011, machine $T_{1}$ enters the sequence of states $q_{1}, q_{2}, q_{2}, q_{2}, q_{2}, q_{1}, q_{1}, q_{1}$ and produces output 1111000. On input abbb, $T_{2}$ outputs 1011. Give the sequence of states entered and the output produced in each of the following parts.

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 $\Sigma$ and an output alphabet $\Gamma$ 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 : Q \times \Sigma \longrightarrow Q \times \Gamma$.)

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. 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, with the two symbols written with a slash, /, separating them. Some transitions may have multiple input-output pairs. When an FST computes on an input string $w$, it takes the input symbols $w_{1} \cdots w_{n}$ one by one and, starting at the start state, follows the transitions by matching the input labels with the sequence of symbols $w_{1} \cdots w_{n}=w$. Every time it goes along a transition, it outputs the corresponding output symbol.

Using the solution you gave to Exercise 1.25, give a formal description of the machines $T_{1}$ and $T_{2}$ depicted in Exercise 1.24.

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 $\left\{ 0,1\right\}$. 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. 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, with the two symbols written with a slash, /, separating them. Some transitions may have multiple input-output pairs. When an FST computes on an input string $w$, it takes the input symbols $w_{1} \cdots w_{n}$ one by one and, starting at the start state, follows the transitions by matching the input labels with the sequence of symbols $w_{1} \cdots w_{n}=w$. Every time it goes along a transition, it outputs the corresponding output symbol.

ᴬ Read the informal definition of the finite state transducer given in Exercise 1.24. Prove that no FST can output $w^{\mathcal{R}}$ for every input $w$ if the input and output alphabets are $\left\{ 0,1\right\}$.

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. 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, with the two symbols written with a slash, /, separating them. Some transitions may have multiple input-output pairs. When an FST computes on an input string $w$, it takes the input symbols $w_{1} \cdots w_{n}$ one by one and, starting at the start state, follows the transitions by matching the input labels with the sequence of symbols $w_{1} \cdots w_{n}=w$. Every time it goes along a transition, it outputs the corresponding output symbol.