matrix characterizations of automata
Let $A=(S,\mathrm{\Sigma},\delta ,I,F)$ be a finite automaton. Recall that $A$ can be visualized by a directed graph^{} ${G}_{A}$ called the state diagram^{} of $A$. The nodes of ${G}_{A}$ are the states of $A$ (elements of $S$), and the edges of ${G}_{A}$ are labeled by the input symbols of $A$ (elements of $\mathrm{\Sigma}$).
Suppose $S=\{{s}_{1},\mathrm{\dots},{s}_{n}\}$. For each symbol $a\in \mathrm{\Sigma}$, we define an $n\times n$ matrix $M(a)$ over the nonnegative integers as follows: the cell
$${M}_{ij}:=\{\begin{array}{cc}1\hfill & \text{if}{s}_{j}\in \delta ({s}_{i},a),\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$ 
In other words, $M(a)$ is a matrix composed of $0$’s and $1$’s, such that cell $(i,j)$ is $1$ provided that there is an edge from node ${s}_{i}$ to ${s}_{j}$ with label $a$. $M$ may be viewed as a function from $\mathrm{\Sigma}$ to the set $\U0001d510(n)$ of $n\times n$ matrices whose entries are $1$’s and $0$’s, mapping $a$ to $M(a)$ just described.
To completely describe $A$, we use two $n$dimensional vectors ${v}_{I}$ and ${v}_{F}$ to specify $I$ and $F$ respectively. The $i$th component^{} of ${v}_{I}$ is $1$ if and only if ${s}_{i}$ is a start state. Otherwise, it is a $0$. ${v}_{F}$ is defined similarly. Thus, the triple $(M,{v}_{I},{v}_{F})$ describes $A$.
The following is the state diagram of an automaton with two states ${s}_{1},{s}_{2}$ over $\{a,b\}$, and its description by matrices:
Conversely, given a triple $(M,v,w)$, where $M:\mathrm{\Sigma}\to \U0001d510(n)$ is a function, and $v,w$ are two $n$dimensional vectors $\{0,1\}$, we can construct an automaton ${A}_{M}$ as follows: ${A}_{M}=(S,\mathrm{\Sigma},\delta ,I,F)$ where

1.
$S$ has $n$ elements ${s}_{1},\mathrm{\dots},{s}_{n}$;

2.
$I$ is a subset of $S$ such that ${s}_{i}\in I$ iff the $i$th component of $v$ is $1$;

3.
$F$ is a subset of $S$ such that ${s}_{j}\in F$ iff the $j$th component of $w$ is $1$;

4.
for each pair $({s}_{i},a)\in S\times \mathrm{\Sigma}$, $\delta ({s}_{i},a)$ is the subset of $S$ such that ${s}_{j}\in \delta ({s}_{i},a)$ iff cell $(i,j)$ of $m(a)$ is $1$.
Let us look more closely now at the function $M$. Given a function $M:\mathrm{\Sigma}\to \U0001d510(n)$, we may extend it in a unique way to a homomorphism^{} from ${\mathrm{\Sigma}}^{*}$ to $\U0001d510{(n)}^{*}$, the monoid of $n\times n$ matrices generated by $\U0001d510(n)$, where the multiplication is defined by the ordinary matrix multiplication^{}. In other words, if ${u}_{1},{u}_{2}$ are words over $\mathrm{\Sigma}$,
$$m({u}_{1}{u}_{2})=m({u}_{1})m({u}_{2}),$$ 
the product of matrices $m({u}_{1})$ and $m({u}_{2})$. We use the same notation $M$ for this extension^{}. In the example above, we see that
$$M({a}^{2})=\left(\begin{array}{ccc}\hfill 0\hfill & \hfill 1\hfill & \\ \hfill 0\hfill & \hfill 1\hfill & \end{array}\right),M(ab)=\left(\begin{array}{ccc}\hfill 1\hfill & \hfill 0\hfill & \\ \hfill 1\hfill & \hfill 0\hfill & \end{array}\right),\text{and}\mathit{\hspace{1em}}M({b}^{2})=\left(\begin{array}{ccc}\hfill 0\hfill & \hfill 0\hfill & \\ \hfill 0\hfill & \hfill 0\hfill & \end{array}\right).$$ 
The following two lemmas are some consequences:
Lemma 1.
For any word $u$ over $\mathrm{\Sigma}$, cell $\mathrm{(}i\mathrm{,}j\mathrm{)}$ of the matrix $M\mathit{}\mathrm{(}u\mathrm{)}$ is the number of paths from ${s}_{i}$ to ${s}_{j}$ with label $u$.
Treating ${v}_{I}$ as a row vector^{} and ${v}_{F}$ as a column vector, we get
Lemma 2.
For any word $u$ over $\mathrm{\Sigma}$,

•
the $i$th component of the row vector ${v}_{I}M(u)$ is the number of paths from a start state to ${s}_{i}$ with label $u$.

•
the $j$th component of the column vector $M(u){v}_{F}$ is the number of paths from ${s}_{j}$ to a final state with label $u$.

•
${v}_{I}M(u){v}_{F}$ is the number of paths from a start state to a final state with label $u$.
Combining the two lemmas, it is easy to see that
Proposition 1.
A language^{} $R$ over $\mathrm{\Sigma}$ is regular^{} iff it can be expressed by a triple $\mathrm{(}M\mathrm{,}v\mathrm{,}w\mathrm{)}$ described above in the following sense:
$$R=\{u\in {\mathrm{\Sigma}}^{*}\mid vM(u)w>0\}$$ 
where $v$ is written as a row vector, and $w$ is written as a column vector.
Title  matrix characterizations of automata 

Canonical name  MatrixCharacterizationsOfAutomata 
Date of creation  20130322 19:02:13 
Last modified on  20130322 19:02:13 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  7 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q05 
Classification  msc 68Q42 
Classification  msc 03D10 