# 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 non-negative 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. 1.

$S$ has $n$ elements $s_{1},\ldots,s_{n}$;

2. 2.

$I$ is a subset of $S$ such that $s_{i}\in I$ iff the $i$-th component of $v$ is $1$;

3. 3.

$F$ is a subset of $S$ such that $s_{j}\in F$ iff the $j$-th component of $w$ is $1$;

4. 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.

Title matrix characterizations of automata MatrixCharacterizationsOfAutomata 2013-03-22 19:02:13 2013-03-22 19:02:13 CWoo (3771) CWoo (3771) 7 CWoo (3771) Definition msc 68Q05 msc 68Q42 msc 03D10