13. Finite state machines and vector recurrences#
At the end of Lecture Note 11 we met counting problems where a recurrence for the total count is hard to find directly: strings with overlapping forbidden substrings, and tilings of a board by dominoes. This note develops a systematic method for such problems. We will carry the following problem through the note.
Problem 1 (Strings avoiding ABA and BC)#
How many strings of length over the alphabet contain neither ABA nor BC as a block of consecutive letters?
Call such a string valid. As in Lecture Note 11, we think of building a string one letter at a time, from left to right, and ask which letters can be written next. Try it with the valid string CAB: writing A next would complete ABA, and writing C would complete BC, so only B can come next. After CCB, the letters A and B can come next. After CBA, all three letters can. So the number of ways to continue depends on how the string built so far ends, and a single total count of valid strings of length does not tell us the total for length . Instead, we will keep a separate count for each kind of ending, find equations linking these counts, and only at the end combine them into a recurrence for the total.
After studying these notes, you will be able to do the following.
Choose states that record the information needed to decide which extensions of a string, walk, or partial tiling are allowed.
Construct a finite state machine and its transition table for a list of forbidden substrings.
Convert a transition table into a transition matrix and a vector recurrence, with the correct initial vector and final sum.
Use the Cayley–Hamilton theorem to derive a scalar recurrence from a vector recurrence, and check where it holds.
Compute a matrix power by repeated squaring and count the multiplications it uses.
Set up boundary states and transition matrices for tilings of a board by dominoes, and by dominoes and angles.
13.1 Finite state machines#
13.1.1 Strings#
A string over a finite alphabet is a finite sequence of letters from , written without commas; its length is the number of letters. The string with no letters at all is called the empty string; it has length , and we denote it by (the Greek letter epsilon), since a blank space on the page would be invisible. Every string is built from by writing its letters one at a time. We write for the string followed by the letter . A substring of is a block of consecutive letters of , a prefix is a block at the start, and a suffix is a block at the end; the empty string counts as all three. A prefix is proper if it is not the whole string. For example, the suffixes of CAB are , B, AB, CAB, and the proper prefixes of ABA are , A, AB.
13.1.2 Keeping notes while building: walks#
We start with an example where the bookkeeping is simple. In Lecture Note 11 we counted walks in with steps , , that never contain LR or RL. A walk is a string over , built one step at a time.
While building a walk, we keep a one-symbol note: the last step taken. Before the first step there is no last step, and we write the note . Once a forbidden pair has been written, the walk is ruined for good, and we write the note (read ``dagger’’). Each new step updates the note according to this table, whose row is the current note and whose column is the step written next: For example, building LUR produces the notes , and the walk is valid. Building ULR produces , and the walk is not valid.
Why does this work? Whether the next step is allowed depends only on the last step, and the note records exactly the last step. So the note always tells us what we need, and we never have to look further back in the walk.
Definition 2 (Deterministic finite state machine)#
A deterministic finite state machine over an alphabet consists of a finite set of states (the possible notes), a start state, a set of accepting states, and a transition function that assigns to each state and letter exactly one next state . The machine reads a string from left to right, starting in the start state and moving from to on each letter . The state reached at the end is the state of the string, and the machine accepts the string if that state is accepting.
The table above is the transition table of the walk machine: its states are , the start state is , and every state except is accepting. Deterministic means that the current state and the next letter decide the next state. Many strings share a state; that is the point, since the state should remember only what affects the future.
13.1.3 A machine for strings avoiding ABA and BC#
For Problem 1, the last letter is not a good enough note: CB and AB both end in B, but A can be written after the first and not after the second. Instead, the note records how much of a forbidden block sits at the end of the string built so far: nothing (), A, B, or AB. The machine is with start state , rejecting state , and the other four states accepting. For example, building CABBA produces so CABBA is valid; building CABA ends with , so CABA is not.
How was the table made? Each entry comes from writing the letter after the state’s name and reading off the new ending. From AB, the letter C gives ABC, which ends in BC, so the entry is . From B, the letter A gives BA; this contains no forbidden block, and the part of a forbidden block at its end is A, so the entry is A. From A, the letter C gives AC, which ends in no part of a forbidden block, so the entry is . In general, the states are the proper prefixes of the forbidden blocks, and from a state the letter leads to if ends in a forbidden block, and otherwise to the longest suffix of that lies in .
Why does this work? A forbidden block is completed by the letter just written, so just before that letter, a proper prefix of the block (an element of ) was sitting at the end of the string. The note records the longest such ending, so it contains every shorter one, and nothing earlier in the string can matter. For instance, CCAB and BBCAB both have note AB and can be continued in exactly the same ways as the string AB itself. Therefore the machine accepts exactly the valid strings. Note that state does not mean the string is empty: after the first letter, it means the string ends in C.
13.2 Counting with a transition matrix#
13.2.1 Strings avoiding ABA and BC#
We now count valid strings separately by state. Let be the numbers of valid strings of length in states ,
A, B, AB. These symbols denote numbers, not strings: for instance is the number of valid strings of length ending in AB, and counts the empty string when and the valid strings ending in C when . The total is .
The counts satisfy with and (the empty string is in state ). Let us use them before explaining them: We can check by hand: of the strings of length , the six of the form or and the string ABA are invalid.
Where do the equations come from? Look at the transition table for the entries equal to B: they are in the rows of , B, and AB, in column B. So a valid string of length in state B is built by writing B after a valid string of length in state , B, or AB. Each such string is built in exactly one way, since removing its last letter recovers the shorter string. Hence , and the other three equations come from the other three states in the same way. Strings in state never contribute, since no letter leads from back to a valid state.
The four equations are one matrix equation. With the states in the order ,
This is a vector recurrence, and is the transition matrix. You can read it directly off the transition table: the entry in the row of state and the column of state is the number of letters leading from to . For instance, the last column has a single , in the row of B, because from AB only the letter B keeps the string valid. For other machines the recipe is the same, and an entry can exceed when several letters lead from to the same .
Since , Sage can compute far ahead. In SageCell, ZZ denotes the integers and a caret denotes a power. Later code blocks use matrices defined in earlier ones, so paste the earlier blocks first.
M = matrix(ZZ, [[1, 1, 0, 0],
[1, 1, 1, 0],
[1, 0, 1, 1],
[0, 1, 0, 0]])
v0 = vector(ZZ, [1, 0, 0, 0])
show([sum(M^n * v0) for n in range(9)])
Sage displays .
13.2.2 Walks#
For walks, let , , be the numbers of valid walks of length ending in L, U, R, and let be the total. Reading the walk table the same way, This gives , , , as in Lecture Note 11. We start at because the start state is used only by the empty walk.
13.3 From a vector recurrence to a scalar recurrence#
The vector recurrence computes , but to use the methods of Lecture Note 12 we want a recurrence for alone. Here is how to get one. Ask Sage for the characteristic polynomial of :
show(M.charpoly('x'))
Sage displays . Read its coefficients as a recurrence of order :
Let us test it on the values computed above: Both agree. This recurrence answers Problem 1. Its negative coefficients do not count anything; they appear because four separate counts have been combined into one equation.
Why does this work? Recall that the characteristic polynomial of a matrix is . We need one theorem from linear algebra, which we use without proof.
Theorem 3 (Cayley–Hamilton)#
Every square matrix satisfies its own characteristic polynomial: if , then the zero matrix.
For example, has , and indeed . For our matrix the theorem says . Multiply this equation on the right by , where . Since , , and so on, we get This is an equation between vectors, so it holds in every coordinate: the sequences , , , all satisfy the same recurrence. Adding the four coordinates gives it for . The same argument works for any matrix.
Theorem 4 (Scalar recurrence from a transition matrix)#
Suppose for , where is a matrix with . Let be a fixed combination of the coordinates of (their sum, or a single coordinate, for example). Then
Two cautions, both visible for walks. Sage gives , hence . First, our vector recurrence for walks starts one step late (its first vector is the one for length ), so the theorem guarantees this only for ; the case must be checked by hand, and it holds: . Second, the recurrence need not be the shortest one: in Lecture Note 11 we found . The two agree, because and the cubic recurrence is the difference of two consecutive instances of the quadratic one.
Remark 5 (Companion matrices)#
Conversely, every recurrence becomes a vector recurrence if we store several consecutive terms. For example, becomes The first row computes the new term; the second row shifts the old term down. This matrix, the companion matrix of the recurrence, has characteristic polynomial , the characteristic polynomial of the recurrence. The same works for any order , with a matrix whose first row holds the coefficients and whose other rows shift.
13.4 Computing matrix powers#
Computing one step at a time takes multiplications by . For very large there is a faster way to compute . Here it is for . Square three times, and then multiply twice, . That is five matrix multiplications instead of the twelve in . This works because in binary (), and .
Definition 6 (Repeated squaring)#
To compute for :
Set , , and .
If is odd, replace by .
Replace by . If , stop and output .
Replace by and go to step 2.
For the procedure carries out exactly the computation above: Why does it work? runs through ; checking whether is odd and then halving it reads the binary digits of from right to left; and collects the powers whose digit is . If has binary digits, there are squarings and at most other multiplications, so at most matrix multiplications in all. We say the count is , meaning at most a constant times . Only , , and are stored.
This counts matrix multiplications, not work on digits. Our counts grow exponentially, so their number of digits grows in proportion to ; for example has digits. If we only need counts modulo a fixed integer, reducing after every multiplication keeps the entries small.
13.5 Tilings of three-row boards#
13.5.1 Tiles and boundary states#
A board has rows from top to bottom and columns . A tiling covers every cell exactly once by tiles lying on the board; tiles may be rotated, and tiles of the same shape are not distinguished. The board has one tiling, the empty one. We use dominoes (two cells sharing a side) and angles (three cells of a square), in all orientations (Figure 1).
Figure 1: The two domino orientations and the four angle orientations. Thin lines separate cells within a tile; thick colored lines outline the tile. The tiling diagrams below use the same convention.#
We build a tiling column by column, the way we built strings letter by letter. Figure 2 follows a domino tiling of the board. After column is finished, a horizontal domino in the top row already covers the top cell of column . Next we fill the rest of column with two horizontal dominoes, in the middle and bottom rows; these stick out and cover the middle and bottom cells of column . And so on, until the board is full and nothing sticks out.
Figure 2: Moving the cut through a domino tiling. The dashed line separates completed columns on the left from the columns still to be processed on the right; only the tiles already placed are colored.#
The note we keep is the set of cells in the next column that are already covered; we call it the boundary state. We record it as a number, so in the figure the states are (top cell covered), then (middle and bottom covered), then at the end. All eight states are shown in Figure 3. Why is this the right note? Tiles placed later only need to avoid the cells already covered; which tiles covered them does not matter. Since dominoes and angles are at most two columns wide, a tile that starts in the current column can reach only the next column, so nothing is covered further to the right.
Figure 3: All eight one-column states, in numerical order. Gray cells are already covered by tiles crossing the cut from the left; white cells still need to be covered. The top, middle, and bottom covered cells contribute , , and , respectively.#
One step of the building process places the tiles whose leftmost column is the current column. They cover its uncovered cells and may stick out into the next column. We call such a set of tiles a filling from to , where is the current state and , the outgoing state, records the cells they cover in the next column. In the figure, two horizontal dominoes form a filling from to .
Now we count exactly as for strings. Let be the number of fillings from to , and let be the matrix with these entries. Then
the entry in row and column of . The reason is the same as for strings: if is the vector of counts of partially built tilings with finished columns, sorted by state, then , because each partially built tiling with columns comes from exactly one with columns plus one filling. We start with nothing placed, in state , and a finished tiling is one with columns and state , since nothing may stick out past the board. Unlike letters, several fillings can join the same two states, so entries of can exceed .
To list the fillings from a state without repeats, we always place next the tile covering the topmost uncovered cell of the column, trying every placement that fits and avoids covered cells.
13.5.2 Dominoes#
Let be the number of domino tilings of the board. Start with an empty column (state ). Its top cell can be covered by a horizontal domino or by a vertical domino. Trying both, there are three fillings: three horizontal dominoes (outgoing state ); a vertical domino on the top two cells and a horizontal one in the bottom row (state ); and a horizontal domino in the top row with a vertical one below it (state ). Next take state , where the top cell is already covered: either a vertical domino fills the rest (state ), or two horizontal dominoes do (state ). Doing this for every state gives the list of outgoing states, shown in Figure 4:
Figure 4: All domino fillings, one panel for each starting state . Each panel shows the starting pattern on the left and every outgoing state of a filling on the right.#
There is a quick way to check this table. The cells a domino filling covers in the next column come from horizontal dominoes, one per row of , so cannot use a row that is already covered in . Every other uncovered cell of the current column needs a vertical domino, which works only if those cells are none, the top two, or the bottom two; and then in only one way. So each pair has at most one filling, and column of the transition matrix has a in each row :
D = matrix(ZZ, [[0, 1, 0, 0, 1, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0]])
show([(D^n)[0, 0] for n in range(11)])
show(D.charpoly('x').factor())
The counts are ; odd widths give because must be even. Figure 5 and Figure 6 show the tilings of widths and .
Figure 5: All three domino tilings of a board: .#
Figure 6: All eleven domino tilings of a board: .#
Sage factors , so Theorem 4 gives a recurrence of order . The last factor suggests something shorter, and indeed Check: and . This answers the question left open in Lecture Note 11.
Why does the shorter recurrence hold? Write for the number of partially built tilings with finished columns in state , so . Starting from state , the table shows that only states ever occur, and flipping a tiling upside down shows that states and have equal counts, as do and . So rows , , , of become Substituting gives and , and eliminating the terms gives .
13.5.3 Dominoes and angles#
Let count tilings by dominoes and angles. The same eight states work; only the fillings change. Figure 7 shows the eleven fillings from state . Some outgoing states repeat: two fillings reach state , one using a top horizontal domino and an angle, the other an angle in the top row and a vertical domino below it. Both count, so the matrix entry in row , column is .
Figure 7: All eleven domino-and-angle fillings from state . Outgoing states that occur more than once give entries of larger than .#
Listing the fillings from every state in the same way gives
E = matrix(ZZ, [[0, 1, 0, 0, 1, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 1, 0],
[0, 1, 0, 0, 1, 1, 0, 0],
[2, 0, 0, 0, 1, 1, 1, 0],
[1, 1, 0, 1, 0, 0, 0, 0],
[2, 0, 1, 0, 0, 0, 0, 0],
[2, 1, 0, 1, 0, 1, 0, 0],
[3, 1, 2, 0, 1, 0, 0, 0]])
show([(E^n)[0, 0] for n in range(9)])
show(E.charpoly('x'))
The counts begin . On the board the three domino tilings are joined by two tilings with two angles (Figure 8). On the board every tiling uses one angle and three dominoes (Figure 9), so an odd number of cells is no longer an obstacle.
Figure 8: The two tilings by two angles. Together with the three domino tilings, they give .#
Figure 9: All eight domino-and-angle tilings of a board: . Each consists of one angle and three dominoes.#
Sage gives . Reading off the coefficients as before gives The terms and are missing because has no or constant term, so this is really a recurrence of order ; but the theorem proves it only for . For we check it directly: and . So it holds for all .
13.6 Summary of the method#
Build the objects one piece at a time: a letter, a step, or a column filling.
Choose states that record what decides the allowed next pieces: the longest suffix that is a proper prefix of a forbidden string, the last step, or the covered cells beyond the cut.
Form the transition matrix, whose entry in row and column counts the pieces leading from to , together with the initial vector and the coordinates to add at the end.
Use the characteristic polynomial to get a scalar recurrence, and check where it starts.
Problem 7 (Overlapping forbidden substrings)#
Let be the number of strings of length over avoiding abca, bcab, and cabc, as at the end of Lecture Note 11. List the proper prefixes of the forbidden strings, build the machine as in Section 13.1.3, write its transition matrix, and use Sage to compute and a recurrence for .