Matrix representation of Automata Is anyone know if there is any tutorial for the matrix representation of automata?? I am taking a theoritical computer science in this semester and the professor uses the matrix in his lecture. I gonna have test next week so I have to study for it. I tried to find any tutorial on good but there was not useful tutorial.. doe anyone know any tutorial??
 A: Let $A = \begin{pmatrix} a & b \\ c & d\end{pmatrix} $ where the entries are alphabet letters and $A_{ij} = a \iff$ there's an $a$ transition from state $i$ to state $j$ labeled $a$.  Then $A^2 = \begin{pmatrix} a^2 + bc & ab + bd \\ ca + dc & cb + d^2\end{pmatrix}$, where $+$ means language union.  Each entry is the language of all $2$-length substrings of your automata from state $i$ to state $j$.  A similar statement holds for $A^k$.
Take the language $b^* a$ which has automata $0 \to^a 1$, $0 \to^b 0$, where $0$ is the starting node and $1$ the final node.  Its matrix looks like
$$
A = 
\begin{pmatrix}
b & a \\
\varnothing & \varnothing
\end{pmatrix}
$$
$$
A^k = \begin{pmatrix}
b^k & b^{k-1} a \\
\varnothing & \varnothing
\end{pmatrix}
$$
Exercise: prove the above characterization.
Let $f(1), \dots f(k)$ be fhe final states of an automaton $A. \ $  Then the language accepted by $A$ can be calculated using its matrix, also called $A$:
Let $B = A^0 + A^1 + \dots \ $  Then $L(A) = B_{1f(1)} + B_{1f(2)} + \dots + B_{1f(k)}$, where $1$ is the starting state.
Let's consider the boolean automata
$1 \rightarrow^0 2 \circlearrowright^1\\
\downarrow^1 \nearrow_0\\
3$
Directly represent it as the matrix $A$ where $A_{ij}$ holds the strings of length $1$ from state $i$ to state $j$:
$$
A = \begin{pmatrix}
\varnothing & 0 & 1 \\
\varnothing & 1 & \varnothing \\
\varnothing & 0 & \varnothing
\end{pmatrix}
$$
A: There is a power point at http://drona.csa.iisc.ernet.in/~deepakd/fmcs-05/MAAT_final.pdf. I am not quite sure if this is what you are looking for or if you have already seen it. There is also this which might be helpful http://planetmath.org/matrixcharacterizationsofautomata. Hopefully one of these can help!
A: I do not quite agree with the second part of EnjoysMath's answer about Boolean representations although I fully agree with the first part.
Let me first remind you the definition of the two operations on the Boolean semiring $\mathbb{B}$. The addition on $\mathbb{B}$ is defined by 
$$
0 + 0 = 0 \text{ and } 0 + 1 = 1 + 0 = 1 + 1 = 1
$$ 
and the multiplication by 
$$
0 \cdot 0 = 0 \cdot 1 = 1 \cdot 0 = 0\text{ and } 1 \cdot 1 = 1
$$
Let $M_n$ be the set of $n \times n$ matrices with entries in $\mathbb{B}$. The product of two such Boolean matrices is defined in the usual way, except that addition and product are of course the Boolean ones. Then $M_n$ is a monoid under the Boolean matrix multiplication.
Let $\mathcal{A} = (Q, A, E, I , F)$ be an automaton (deterministic or not) with $n$ states.
The Boolean representation of $\mathcal{A}$ is the monoid homomorphism $\mu$ from $A^*$ into $M_n$ defined as follows: for each letter $a \in A$, $\mu(a) = \bigl(\mu(a)_{p,q}\bigr)_{(p, q) \in Q^2}$ is the matrix defined by
$$
  \mu(a)_{p,q} = \begin{cases}
    1 & \text{if there is a transition $p \xrightarrow{a} q$} \\
    0 & \text{otherwise}
\end{cases}
$$
Since $\mu$ is a monoid morphism, this suffices to define $\mu$ on $A^*$ ($\mu(1)$ is the identity matrix and $\mu(a_1 \dotsm a_k) = \mu(a_1) \dotsm \mu(a_k)$, but $\mu(u)$ can be also defined directly by setting
$$
  \mu(u)_{p,q} = \begin{cases}
    1 & \text{if there is a path $p \xrightarrow{u} q$} \\
    0 & \text{otherwise}
\end{cases}
$$
See this paper, Section 4.
