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!