3
$\begingroup$

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:

state-machine 1

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

state-machine 2

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!

  • 0
    I think you're missing a loop with 'c' from $q_0$ to itself?2011-06-26
  • 0
    @joriki You were right, thank you. I just corrected it above2011-06-26

1 Answers 1

1

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).

  • 0
    @gadi-a thank you, I corrected my approach above, could you please check it again?2011-06-26
  • 0
    I think you miss the main point - a Generating function is NOT an explicit formula. For example, the G.F 1/(1-t) describes the series 1+t+t^2+... which "encodes" the sequence 1,1,1,..., whose explicit formula is simply a_n=1. Therefore, by finding the G.F. you solve (a), not (b).2011-06-26
  • 0
    @gadi-a and how do I do this? I don't see the relationshop with the transfer-matrix-method (that we explicitly should use)2011-06-26
  • 0
    The transfer matrix method gives you the generating function. Once you have found it, you can attempt to expand it into power series using several algebraic tricks that merit a different answer (or question...). It really depends on the generating function you found. A recurrence relation is always easy to obtain from GF's obtained by transfer-matrix, but explicit formula - I don't think so.2011-06-26
  • 0
    @gadi-a now I am completely confused. First of all - is my attempt to get $g_n = f_{q_0 q_0} + f_{q_0 q_1} + f_{q_0 q_2}$ now correct? So if I understand you properly the next steps for me are: 1) Get $g_n$ using the transfer-matrix-method as described above 2) Do some "algebraic magic" to identify a corresponding power series for $g_n$ 3) This result is the solution for part (b) 4) It might be used to prove (a) as well. Is it what I should do and correct this time?2011-06-26
  • 0
    By summing up the f's you won't get g_n - g_n is a number dependent on n - you'll get a function in the variable x, which we'll denote as g(x). This g(x) is the solution of (a). The point is that g(x), when expanded to a power series, is of the form \sum g_n*x^n with g_n being the elements of the sequence you're after.2011-06-26
  • 0
    A final suggestion - try reading a little more about generating functions in general. This is a confusing subject, and it's better to be well-understood before studying computational techniques like transfer-matrix.2011-06-26
  • 0
    @Gadi-A I extended my main question above by this. Could you please take a look at it as there is still something wrong. I will take account of your advice and look at (b) after reading more about it.2011-06-26