Let $G = (V,E,\Phi)$ be a weighted directed graph and $\mathcal{W}' : E \rightarrow \mathbb{C}$ the weighting. Let additionally $m = \# V$, $E_m$ the $m \times m$ identity matrix. Let $v,w \in V$ be in a fixed order in $V$ so $v$ is the i-th and $w$ the j-th element of $V$. Then applies
$$f_{vw}(x) = (-1)^{i+j} \det((E_m – xA)^{(j,i)}) / \det(E_m-xA).$$
Example:
Let $L$ be the set of all words over the alphabet $\Sigma = \{a,b\}$ that no not contain "bb". The following unique finite state-machine with the start state $S = q_0$ and final states $T = \{q_0,q_1\}$ accepts exactly these language:
we now use a weighting $W'(e) = 1$. The matrix of the graph is given by
$$\mathcal{A} = \left(
\begin{array}{cc} 1 & 1 \\
1 & 0
\end{array}
\right)
$$
while the first row and column relate to the node $q_0$ and the second row and column to the node $q_1$. Then applies for $f_L(x) = \sum_{n \geq 0} \sum_{w \in L \atop |w| = n} x^n$ that $f_L(x) = f_{q_0q_0}(x)+f_{q_0q_1}(x)$.
Because of $$\det(E_2-Ax) = (1-x)-x^2$$ we get using the the transfer-matrix-method (see definition above)$$f_{q_0q_0}(x) = (-1)^{1+1} \det((E_2-Ax)^{(1,1)})/\det(E_2-Ax) = 1/(1-x->x^2).$$
$$f_{q_0q_1}(x) = (-1)^{1+2} \det((E_2-Ax)^{(2,1)})/\det(E_2-Ax) = (-1) \cdot (-x)/(1-x-x^2).$$
Therefore applies
$$f_L(x)=f_{q_0q_0}(x) +f_{q_0q_1}(x) = \frac{1+x}{1-x-x^2}.$$Exercise
Let $g_n$ be the amount of words of the length $n$ over the alphabet $\Sigma = \{a,b,c\}$ that do not contain $ab,ac,bc$ or $ba$. Use the transfer-matrix-method.
(a) Prove that $\sum_{n\geq 0} g_n t^n = \frac{1+t}{(1-t)^2}$
(b) Identifiy an explicit formula for $g_n, n \geq 0$
Hi!
Sorry for the long introduction, but I just was not sure if your definitions and conventions match with the ones I have to use.
We didn't get more information about the "transfer-matrix-method" then I wrote above, and I still don't get it completely.
I created the finite state machine for the given language as
The matrix of the corresponding graph according to the example would be
$$\mathcal{A} = \left(
\begin{array}{ccc} 1 & 1 & 0 \\
1 & 1 & 1 \\
1 & 0 & 1
\end{array}
\right)
$$.
$\begin{eqnarray*}
f_{q_0 q_0}(x) &=& (-1)^{1+1} \det((E_m – xA)^{(1,1)}) / \det(E_m-xA) \\
&=& \det \left(\left( \left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{array} \right)
– \left(\begin{array}{ccc} x & x & 0 \\ x & x & x \\ x & 0 & x\end{array} \right)\right)^{(1,1)}
\right) \\ && / \det \left( \left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{array} \right)
– \left(\begin{array}{ccc} x & x & 0 \\ x & x & x \\ x & 0 & x\end{array} \right)\right) \\
&=& \det \left( \begin{array}{ccc} (1-x) & (-x) & 0 \\ (-x) & (1-x) & (-x) \\ (-x) & 0 & (1-x) \end{array}
\right)^{(1,1)} \\ &&/ \det \left( \begin{array}{ccc} (1-x) & (-x) & 0 \\ (-x) & (1-x) & (-x) \\ (-x) & 0 & (1-x) \end{array}
\right) \\
&=& \det \left( \begin{array}{ccc} (1-x) & (-x) \\ 0 & (1-x) \end{array} \right) / \det \left( \begin{array}{ccc} (1-x) & (-x) & 0 \\ (-x) & (1-x) & (-x) \\ (-x) & 0 & (1-x) \end{array}
\right) \\
&=& (1-x)^2 / ((1-x)^3 + (-x)^3 – (-x)(-x)(1-x)) \\
&=& \frac{(1-x)^2}{-x^3 -x^2 (1-x)+(1-x)^3} \\
f_{q_0 q_1}(x) &=& (-1)^{1+2} \det((E_m – xA)^{(2,1)}) / \det(E_m-xA) \\
&=& (-1) \det \left( \begin{array}{ccc} (1-x) & (-x) & 0 \\ (-x) & (1-x) & (-x) \\ (-x) & 0 & (1-x) \end{array}
\right)^{(2,1)} / \det(E_m-xA) \\
&=& (-1) \det \left( \begin{array}{cc} (-x) & 0 \\ 0 & (1-x)\end{array}
\right)^{(2,1)} / \det(E_m-xA) \\
&=& (-1) (-x)(1-x) / -x^3 -x^2 (1-x)+(1-x)^3 \\
&=& \frac{(1-x)x}{-x^3 -x^2 (1-x)+(1-x)^3} \\
f_{q_0 q_2}(x) &=& (-1)^{1+3} \det((E_m – xA)^{(3,1)}) / \det(E_m-xA) \\
&=& \det \left( \begin{array}{cc} (-x) & 0 \\ (1-x) & (-x) \end{array}
\right) / \det(E_m-xA) \\
&=& \frac{x^2}{-x^3 -x^2 (1-x)+(1-x)^3} \\
f_{q_0 q_0} + f_{q_0 q_1} + f_{q_0 q_2} &=& \frac{(1-x)^2 + (1-x) x+ x^2}{-x^3 -x^2 (1-x)+(1-x)^3}
\end{eqnarray*}
$
So $\frac{(1-x)^2 + (1-x) x+ x^2}{-x^3 -x^2 (1-x)+(1-x)^3}$ should the answer to (a), shoudn't it? Unfortunately (according to Wolfram Alpha) it isn't. Is there still anything wrong?
Thanks in advance!
Best Answer
You miss an edge with "c" from q_0 to itself. Afterwards, note that to compute $f_{q_0q_0}$ (and the others) you need to compute two determinants - one of $E_3-xA$, but the other of a minor of that matrix. Then you need to divide them (all this follows from Carmer's rule for inverting matrices).