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 non-negative integers as follows: the cell

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 $𝔐(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 𝔐(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 𝔐(n)$, we may extend it in a unique way to a homomorphism from ${\mathrm{\Sigma }}^{*}$ to $𝔐{(n)}^{*}$, the monoid of $n\times n$ matrices generated by $𝔐(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

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	2013-03-22 19:02:13
Last modified on	2013-03-22 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