TAOCP 7.1.2 Exercise 43

Section 7.1.2: Boolean Evaluation

Exercise 43. ▶ [28] A finite-state transducer is an abstract machine with a finite input alphabet $A$, a finite output alphabet $B$, and a finite set of internal states $Q$. One of those states, $q_0$, is called the "initial state." Given a string $\alpha = a_1 \ldots a_n$, where each $a_j \in A$, the machine computes a string $\beta = b_1 \ldots b_n$, where each $b_j \in B$, as follows:

T1. [Initialize.] Set $j \leftarrow 1$ and $q \leftarrow q_0$.

T2. [Done?] Terminate the algorithm if $j > n$.

T3. [Output $b_j$.] Set $b_j \leftarrow c(q, a_j)$.

T4. [Advance $j$.] Set $q \leftarrow d(q, a_j)$, $j \leftarrow j + 1$, and return to step T2. ∎

The machine has built-in instructions that specify $c(q, a) \in B$ and $d(q, a) \in Q$ for every state $q \in Q$ and every character $a \in A$. The purpose of this exercise is to show that, if the alphabets $A$ and $B$ of any finite state transducer are encoded in binary, the string $\beta$ can be computed from $\alpha$ by a Boolean chain of size $O(n)$ and depth $O(\log n)$.

a) Consider the problem of changing a binary vector $a_1 \ldots a_n$ to $b_1 \ldots b_n$ by setting

$$b_j \leftarrow a_j \oplus [a_j = a_{j-1} = \cdots = a_{j-k} = 1 \text{ and } a_{j-k-1} = 0, \text{ where } k \ge 1 \text{ is odd}],$$

assuming that $a_0 = 0$. For example, $\alpha = 11001001000111111101101010 \mapsto \beta = 10001001000101010010101010$. Prove that this transformation can be carried out by a finite-state transducer with $|A| = |B| = |Q| = 2$.

b) Suppose a finite-state transducer with $|Q| = 2$ is in state $q_j$ after reading $a_1 \ldots a_{j-1}$. Explain how to compute the sequence $q_1 \ldots q_n$ with a Boolean chain of cost $O(n)$ and depth $O(\log n)$, using the construction of Ladner and Fischer in exercise 36. (From this sequence $q_1 \ldots q_n$ it is easy to compute $b_1 \ldots b_n$, since $b_j = c(q_j, a_j)$.)

c) Apply the method of (b) to the problem in (a).

Verified: yes
Solve time: 5m19s

Corrected Solution

Let the transducer be applied to input $a_1\cdots a_n$, producing outputs $b_1\cdots b_n$, with state sequence $q_0,q_1,\ldots,q_n$ defined by

$$ q_j = d(q_{j-1},a_j), \quad b_j = c(q_{j-1},a_j), $$

as required by the model.

We now correct each part.

(a) Construction of a 2-state finite-state transducer

We first rewrite the transformation in a form consistent with the timing of the FST.

Step 1: Understanding the condition

The problem defines $b_j$ by flipping $a_j$ when there exists an odd $k\ge 1$ such that

$$ a_j=a_{j-1}=\cdots=a_{j-k}=1,\quad a_{j-k-1}=0. $$

This means that the block of consecutive 1s ending at position $j$ has length $k+1$, where $k$ is odd. Hence the block length is even and at least 2.

So the condition is:

$$ b_j = a_j \oplus P(j), $$

where $P(j)=1$ iff the run of consecutive 1s ending at $j$ has even length at least 2.

Let $r_j$ be the length of the current run of 1s ending at position $j$ (reset to 0 after a 0).

Then:

if $a_j=0$, $r_j=0$
if $a_j=1$, $r_j=r_{j-1}+1$

The condition becomes:

$$ P(j)=1 \iff a_j=1 \text{ and } r_{j-1} \text{ is odd}. $$

Thus the output depends only on $a_j$ and the previous state $q_{j-1} = r_{j-1} \bmod 2$.

Step 2: Define the 2 states

Let

$$ Q={0,1}, $$

where:

$q=0$: even length of current run of 1s since last 0
$q=1$: odd length of current run of 1s since last 0

Initial state: $q_0=0$.

Step 3: Transition function

Update parity of run length:

$$ d(q,0)=0,\quad d(q,1)=1-q. $$

Explanation:

reading 0 resets the run
reading 1 toggles parity

Step 4: Output function (correct timing)

We must use $q_{j-1}$, not $q_j$.

We have:

flip occurs exactly when $a_j=1$ and $q_{j-1}=1$

Thus:

$$ b_j = a_j \oplus (a_j \land q_{j-1}). $$

Simplify:

$$ x \oplus (x \land y) = x \land \neg y. $$

Hence:

$$ c(q,a)= a \land \neg q. $$

Step 5: Correctness

If $a_j=0$, then $b_j=0$.
If $a_j=1$, then:
if $q_{j-1}=0$: no flip, $b_j=1$
if $q_{j-1}=1$: flip, $b_j=0$

This matches exactly the required transformation.

Thus the machine is a valid finite-state transducer with:

$$ |A|=|B|=|Q|=2. $$

(b) Parallel computation of the state sequence

We compute $q_1,\ldots,q_n$ using Ladner–Fischer prefix computation.

Step 1: View transitions as functions

For each input symbol $a_j$, define:

$$ f_{a_j}:Q\to Q,\quad f_{a_j}(q)=d(q,a_j). $$

Thus:

$f_0(q)=0$
$f_1(q)=1-q$

The state evolution is:

$$ q_j = (f_{a_j}\circ f_{a_{j-1}}\circ \cdots \circ f_{a_1})(q_0). $$

Define prefix functions:

$$ F_j = f_{a_j}\circ \cdots \circ f_{a_1}. $$

Then:

$$ q_j = F_j(q_0). $$

Step 2: Apply Ladner–Fischer prefix computation

The set of all functions $Q\to Q$ has constant size (4 possible Boolean functions). Composition is associative, so we may compute all prefix products $F_j$ in:

size $O(n)$
depth $O(\log n)$

using the standard Ladner–Fischer parallel prefix circuit.

Step 3: Recover states

Once $F_j$ is computed:

$$ q_j = F_j(q_0) $$

for all $j$, in parallel with $O(n)$ additional work and no increase in asymptotic depth.

(c) Application to the specific transducer

From part (a):

states encode parity of run length of 1s
transitions are:

$$ f_0(q)=0,\quad f_1(q)=1-q $$

output is:

$$ b_j = a_j \land \neg q_{j-1}. $$

Step 1: Compute states

Apply part (b) to compute all $q_j$ in:

$O(n)$ size
$O(\log n)$ depth

Step 2: Compute outputs

For each $j$, compute in parallel:

$$ b_j = a_j \land \neg q_{j-1}. $$

This is a constant-size Boolean operation per position, so it preserves:

total size $O(n)$
depth $O(\log n)$

Conclusion

The finite-state transducer in part (a) is correctly defined with outputs depending on $q_{j-1}$, as required.
The state sequence can be computed via associative prefix composition over a finite set of functions.
The full output sequence follows by a single additional layer of Boolean operations.

Therefore, the transformation is computable by a Boolean chain of size $O(n)$ and depth $O(\log n)$.