You are here
Homematrix characterizations of automata
Primary tabs
matrix characterizations of automata
Let $A=(S,\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 $\Sigma$).
Suppose $S=\{s_{1},\ldots,s_{n}\}$. For each symbol $a\in\Sigma$, we define an $n\times n$ matrix $M(a)$ over the nonnegative integers as follows: the cell
$M_{{ij}}:=\left\{\begin{array}[]{ll}1&\textrm{if }s_{j}\in\delta(s_{i},a),\\ 0&\textrm{otherwise.}\end{array}\right.$ 
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 $\Sigma$ to the set $\mathfrak{M}(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:\Sigma\to\mathfrak{M}(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,\Sigma,\delta,I,F)$ where
1. $S$ has $n$ elements $s_{1},\ldots,s_{n}$;
2. 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\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:\Sigma\to\mathfrak{M}(n)$, we may extend it in a unique way to a homomorphism from $\Sigma^{*}$ to $\mathfrak{M}(n)^{*}$, the monoid of $n\times n$ matrices generated by $\mathfrak{M}(n)$, where the multiplication is defined by the ordinary matrix multiplication. In other words, if $u_{1},u_{2}$ are words over $\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}0&1\\ 0&1\end{array}\right),\quad M(ab)=\left(\begin{array}[]{ccc}1&0\\ 1&0\end{array}\right),\quad\mbox{and}\quad M(b^{2})=\left(\begin{array}[]{ccc}% 0&0\\ 0&0\end{array}\right).$ 
The following two lemmas are some consequences:
Lemma 1.
For any word $u$ over $\Sigma$, cell $(i,j)$ of the matrix $M(u)$ 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 $\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 $\Sigma$ is regular iff it can be expressed by a triple $(M,v,w)$ described above in the following sense:
$R=\{u\in\Sigma^{*}\mid vM(u)w>0\}$ 
where $v$ is written as a row vector, and $w$ is written as a column vector.
Mathematics Subject Classification
68Q05 no label found68Q42 no label found03D10 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections