Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
I think you're missing a loop with 'c' from $q_0$ to itself? –  joriki Jun 26 '11 at 13:12
    
@joriki You were right, thank you. I just corrected it above –  muffel Jun 26 '11 at 17:58
add comment

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer
    
@gadi-a thank you, I corrected my approach above, could you please check it again? –  muffel Jun 26 '11 at 17:58
    
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). –  Gadi A Jun 26 '11 at 18:40
    
@gadi-a and how do I do this? I don't see the relationshop with the transfer-matrix-method (that we explicitly should use) –  muffel Jun 26 '11 at 18:45
    
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. –  Gadi A Jun 26 '11 at 20:07
    
@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? –  muffel Jun 26 '11 at 20:25
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.