Finite Automata: Transducers and Recognizers

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

Determine which languages can be recognized by deterministic finite automata with alphabet $\Sigma =\left\{ 0,1\right\}$ and state set $Q=\left\{ q_{0}, q_{1}\right\}$.

Let $\Sigma =\left\{ a, b\right\} , Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}\right\} , F=\left\{ q_{3}, q_{4}\right\}$, and let the transition function $P_{1}$ of the finite automaton $\mathfrak {M}=\left(Q, \Sigma , P_{1}, q_{0}, F\right)$ be given by the table shown in Fig. 24. Determine which of the following three words are recognized by the automaton $\mathfrak {M}: w=a a a b b a b a b, v=b a b b b a b b a$, $u=a b a b a a a b?$

The language $L$ consists of all words that begin with the letter $b$ and contain a number of letters $a$ that is a multiple of three. Determine which of the following three deterministic finite automata recognize the language $L: \mathfrak {M}_{i}=\left(\left\{ q_{0}, q_{1}, q_{2}, q_{3}, q_{4}\right\} ,\left\{ a, b\right\} , P_{i}, q_{0},\left\{ q_{1}\right\} \right), i=2,3,4$, whose programs $P_{i}$ are given by the table shown in Fig. 24.

The components of the finite automaton $\mathfrak {M}=\left(Q, \Sigma , P_{5}, q_{0}, F\right)$ are $Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}\right\} , \Sigma =\left\{ a, b\right\} , F=\left\{ q_{3}\right\}$, and the program $P_{5}$ is given by the table in Fig. 24. Prove that the automaton $\mathfrak {M}$ recognizes the language consisting

precisely of those words in the alphabet $\left\{ a, b\right\}$ that end with the fragment $a b a$.

Prove that the automaton shown in Fig. 25 recognizes the language consisting of all words that end in $b a$ and do not contain $a a$.

Fig. 25: Automaton from Problem 442.

By induction on the length of the word $w$, prove the following statement: $(q, w x) \vdash_{\mathfrak {M}}^{*}(p, x)$ if and only if there is a path in $\mathfrak {D}_{\mathfrak {M}}$ from $q$ to $p$ carrying $w$.

Construct deterministic finite automata that recognize the following languages over the alphabet $\Sigma =\left\{ a, b\right\}$:

Construct a deterministic finite automaton that verifies the correctness of addition. The input is a sequence of "three-story" symbols, in which the top level holds a digit of the first addend, the middle level a digit of the second addend, and the bottom level a digit of the proposed sum. The automaton must accept the word if the result of the addition written on the bottom level is correct. The digits of all the numbers are written in order of increasing place value.

Construct deterministic finite automata recognizing the following languages over the alphabet $\left\{ 0,1\right\}$:

Construct a deterministic finite automaton $\mathfrak {M}$ with alphabet $\Sigma =\left\{ \wedge , \vee , 0,1\right\}$ that accepts only those words which are true DNFs.

Two languages are given over the alphabet $\Sigma =\left\{ a, b\right\}$:

Let $\mathfrak {M}=(Q, \Sigma , P, q,\left\{ p\right\} )$ be a nondeterministic finite automaton, where $Q=\left\{ q, p, s\right\} , \Sigma =\left\{ 0,1\right\} , P=\left\{ q, 0 \rightarrow p ; q, 0 \rightarrow s ; q, 1 \rightarrow q ; p, 0 \rightarrow q ; p, 0 \rightarrow p ; s, 1 \rightarrow q ; s, 1 \rightarrow p\right\}$.

Determine which of the following three deterministic automata $\mathfrak {M}_{i}=\left(Q_{i}, \Sigma , P_{i}, q, F_{i}\right)$ are equivalent to $\mathfrak {M}$:

Using the determinization procedure, construct deterministic automata equivalent to the following nondeterministic finite automata $\mathfrak {N}$ with alphabet $\Sigma =\left\{ a, b\right\}$:

Let $\mathfrak {M}=\left(Q, \Sigma , P, q_{0}, F\right)$ be a nondeterministic finite automaton, in which $Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}\right\} , \Sigma =\left\{ a, b\right\} , F=\left\{ q_{1}, q_{3}\right\}$, $P=\left\{ q_{0}, a \rightarrow q_{0} ; q_{0}, a \rightarrow q_{1} ; q_{0}, b \rightarrow q_{2} ; q_{1}, b \rightarrow q_{0} ; q_{2}, a \rightarrow q_{0} ; q_{2}, a \rightarrow q_{3} ; q_{2}, b \rightarrow q_{1} ; q_{2}, b \rightarrow q_{2} ; q_{2}, b \rightarrow q_{3} ; q_{3}, a \rightarrow q_{0} ; q_{3}, a \rightarrow q_{3}\right\}$.

Let $\mathfrak {M}=\left(Q, \Sigma , P, q_{0}, F\right)$ be a nondeterministic finite automaton, where $Q=\left\{ q_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}\right\} , \Sigma =\left\{ 0,1\right\} , F=\left\{ q_{5}\right\}$, and $P$ is defined in the table in Fig. 26 on the facing page (a dash means the absence of the corresponding transitions).

Apply the determinization procedure and construct a deterministic automaton equivalent to the nondeterministic finite automaton shown in Fig. 27.

Fig. 27: Automaton from Problem 453.

The language $L$ over the alphabet $\Sigma =\left\{ a_{1}, \ldots , a_{k}\right\}$ consists of all words in which at least one letter of the alphabet $\Sigma$ is missing.

A nondeterministic finite automaton $\mathfrak {N}=\left(Q, \Sigma , P, q_{0}, F\right)$ over the alphabet $\Sigma =\left\{ a, b, c\right\}$ with $n$ states $Q=\left\{ q_{0}, q_{1}, \ldots , q_{n-1}\right\}$ and set of accepting states $F=\left\{ q_{0}\right\}$ is shown in Fig. 28.

Fig. 28: Automaton from Problem 455.

Let $\mathfrak {M}=\left(\mathrm{P}(Q), \Sigma , P^{\prime },\left\{ q_{0}\right\} , F^{\prime }\right)$ be the automaton obtained from $\mathfrak {N}$ via the determinization procedure. Prove that