Finite Automata

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

Prove that the automaton $\mathfrak {M}$ shown in Fig. 83 on p. 307 recognizes the language consisting of all words ending in "aba".

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 in $\mathfrak {D}_{\mathfrak {M}}$ there is a path from $q$ to $p$ carrying $w$. Derive from it Lemma 96 on p. 293.

Lemma 96: The automaton $\mathfrak {M}$ accepts the word $w$ if and only if in the diagram $\mathfrak {D}_{\mathfrak {M}}$ there is a path carrying $w$ from the initial state $q_{0}$ to some accepting state $q \in F$, that is, $w$ takes $q_{0}$ to an accepting state $q$.

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

Above, in Example 68 on p. 288, a transducer performing the addition of two binary numbers was constructed. Construct a deterministic finite automaton that checks the correctness of the addition. The input consists of "three-level" symbols, in which the top level contains a digit of the first addend, the middle level a digit of the second addend, and the bottom level a digit of the presumed sum. The automaton should accept the word if the result of the addition written on the bottom level is correct. The digits of all numbers are written in order of increasing place value.

Prove Lemma 97 on p. 297.

Definition 126 (Product of automata): Let $\mathfrak {M}_{1}=(Q_{1}, \Sigma , P_{1}, q_{0}^{1}, F_{1})$ and $\mathfrak {M}_{2}=(Q_{2}, \Sigma , P_{2}, q_{0}^{2}, F_{2})$ be two finite automata with a common input alphabet $\Sigma$. A product of the automata $\mathfrak {M}_{1}$ and $\mathfrak {M}_{2}$ is any automaton $\mathfrak {N}$ of the form $\mathfrak {N}=(Q_{1} \times Q_{2}, \Sigma , P, (q_{0}^{1}, q_{0}^{2}), F)$, whose program $P$ contains the command $(q_{1}, q_{2}), a \rightarrow (p_{1}, p_{2})$ whenever $q_{1}, a \rightarrow p_{1} \in P_{1}$ and $q_{2}, a \rightarrow p_{2} \in P_{2}$. (No condition is imposed on the set of accepting states $F$ of $\mathfrak {N}$, so a product is not a uniquely determined operation — different choices of $F$ give different automata.)

Lemma 97: If $\mathfrak {N}$ is a product of $\mathfrak {M}_{1}$ and $\mathfrak {M}_{2}$, then for any two states $(q_{1}, q_{2})$ and $(p_{1}, p_{2})$ of $\mathfrak {N}$ and any input word $w$, the following holds: $w$ takes $(q_{1}, q_{2})$ to $(p_{1}, p_{2})$ in the automaton $\mathfrak {N}$ if and only if $w$ simultaneously takes $q_{1}$ to $p_{1}$ in $\mathfrak {M}_{1}$ and $q_{2}$ to $p_{2}$ in $\mathfrak {M}_{2}$.

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

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. 85 on the next page. Let $\mathfrak {M}=\left(\mathrm{P}(Q), \Sigma , P^{\prime },\left\{ q_{0}\right\} , F^{\prime }\right)$ be the automaton obtained from $\mathfrak {N}$ by applying the determinization procedure. Prove that

Fig. 85. Automaton from Problem 246.