# Is my understanding of "subshifts of finite type" correct?

I am reading some lecture notes on Dynamical Systems, and I arrived at subshifts of finite type (ssft). The professor defines $$\sum_n^+$$ as the set of all one-sided sequences $$.s_0s_1s_2...$$ where for each $$i$$, $$s_i \in \{0, 1, 2, ..., n-1\}.$$ Then, let $$A$$ be any $$n \times n$$ matrix whose entries are in $$\{0, 1\}$$. Then the notes define the subshift of finite type corresponding to A as

$$\{\underline{s} = s_0 s_1 s_2...|\forall i: A_{s_i, s_{i+1}} = 1\}$$

I would like to show an example to make sure I understood the definition clearly. Let $$A$$ be the matrix $$A = \begin{bmatrix} 1 & 1 & 0\\ 0 & 1 & 1\\ 1 & 1 & 0 \end{bmatrix}$$

I think we are supposed to label the rows as row 0, row 1, row 2, and the columns as col 0, col 1, col 2. N. We have $$1 = A_{00} = A_{01} = A_{11} = A_{12} = A_{20} = A_{21}$$ $$0 = A_{02} = A_{10} = A_{22}$$ Therefore the sequences in $$\sum_A^+$$ are exactly those whose size-2 blocks are on this list: $$00, 01, 11, 12, 20, 21$$. So for example, an element of $$\sum_A^+$$ is $$.00011120000000...$$ But an element not in $$\sum_A^+$$ is $$.000020000.....$$

Is my understanding of ssft correct? Thank you so much!

• That’s how I understand it. Sep 25, 2020 at 1:57
• @BrianM.Scott Thank you very much! Sep 25, 2020 at 13:57
• My pleasure; it was a new term for me until a couple of days ago. Sep 25, 2020 at 16:11

Yes, your understanding is correct. The set $$\sum_n^+$$ contains all one-sided infinite sequences over the alphabet $$\{0, \ldots, n-1\}$$. Sometimes it's useful to instead consider two-sided sequences: so the phrase "subshift of finite type", by itself, can be ambiguous. Your $$\sum_A^+$$ is a one-sided subshift of finite type. Also, when people say "subshift of finite type" they're usually talking about a slightly more complicated structure: not just the set of sequences, but also a particular topology on that set (namely, the one induced by the Tychonoff product topology on $$\Sigma_n^+$$) and a shift map $$\sigma$$, which slides a sequence to the left (or, in the one-sided case, deletes the first symbol: e.g., $$\sigma(.121000\ldots) = .21000\ldots$$).
The thing that makes it of "finite type" is that it can also be defined by a finite set of rules. An equivalent way of defining $$\sum_A^+$$ is to take all sequences that do not contain the forbidden words '02', '10', or '22'. If we wanted to, we could also forbid longer words like '01210'. The forbidden-words definition is more general: If we were to forbid longer words, there might not be a way of specifying the rule via a transition matrix. There is no matrix $$A$$ for which $$\Sigma_A^+$$ consists of all sequences that do not contain '01210'.