matrix characterizations of automata

Let A=(S,Σ,δ,I,F) be a finite automaton. Recall that A can be visualized by a directed graphMathworldPlanetmath GA called the state diagramMathworldPlanetmathPlanetmath of A. The nodes of GA are the states of A (elements of S), and the edges of GA are labeled by the input symbols of A (elements of Σ).

Suppose S={s1,,sn}. For each symbol aΣ, we define an n×n matrix M(a) over the non-negative integers as follows: the cell

Mij:={1if sjδ(si,a),0otherwise.

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 si to sj with label a. M may be viewed as a function from Σ to the set 𝔐(n) of n×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 vI and vF to specify I and F respectively. The i-th componentMathworldPlanetmathPlanetmathPlanetmath of vI is 1 if and only if si is a start state. Otherwise, it is a 0. vF is defined similarly. Thus, the triple (M,vI,vF) describes A.

The following is the state diagram of an automaton with two states s1,s2 over {a,b}, and its description by matrices:

Conversely, given a triple (M,v,w), where M:Σ𝔐(n) is a function, and v,w are two n-dimensional vectors {0,1}, we can construct an automaton AM as follows: AM=(S,Σ,δ,I,F) where

  1. 1.

    S has n elements s1,,sn;

  2. 2.

    I is a subset of S such that siI iff the i-th component of v is 1;

  3. 3.

    F is a subset of S such that sjF iff the j-th component of w is 1;

  4. 4.

    for each pair (si,a)S×Σ, δ(si,a) is the subset of S such that sjδ(si,a) iff cell (i,j) of m(a) is 1.

Let us look more closely now at the function M. Given a function M:Σ𝔐(n), we may extend it in a unique way to a homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath from Σ* to 𝔐(n)*, the monoid of n×n matrices generated by 𝔐(n), where the multiplication is defined by the ordinary matrix multiplicationMathworldPlanetmath. In other words, if u1,u2 are words over Σ,


the product of matrices m(u1) and m(u2). We use the same notation M for this extensionPlanetmathPlanetmathPlanetmath. In the example above, we see that


The following two lemmas are some consequences:

Lemma 1.

For any word u over Σ, cell (i,j) of the matrix M(u) is the number of paths from si to sj with label u.

Treating vI as a row vectorMathworldPlanetmath and vF as a column vector, we get

Lemma 2.

For any word u over Σ,

  • the i-th component of the row vector vIM(u) is the number of paths from a start state to si with label u.

  • the j-th component of the column vector M(u)vF is the number of paths from sj to a final state with label u.

  • vIM(u)vF 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 languagePlanetmathPlanetmath R over Σ is regularPlanetmathPlanetmathPlanetmath iff it can be expressed by a triple (M,v,w) described above in the following sense:


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