Transfer Matrix Method to determine the generating function

Question

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 contain max two b's.

(a) Use the transfer-matrix-method to determine the generating function $\sum_{n\geq 0} a_n x^n$

(b) Determine an explicit formula for $a_n$

I created the finite state machine for the given language as

$$ \mathcal{A}= \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{pmatrix} $$

\begin{align*} f^G_{11}(x) &= \frac{ (-1)^{1+1}\det((E_m - xA)^{(1,1)})}{\det(E_m-xA)}\\ &=\frac{\det\left(\left( \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix}- \begin{pmatrix} x & x & 0 \\ 0 & x & x \\ 0 & 0 & x \\ \end{pmatrix} \right)^{(1,1)}\right)} {\det\left(\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix}- \begin{pmatrix} x & x & 0 \\ 0 & x & x \\ 0 & 0 & x \\ \end{pmatrix} \right)} \\ &=\frac{\det\begin{pmatrix} 1-x & -x & 0 \\ 0 & 1-x & -x \\ 0 & 0 & 1-x \\ \end{pmatrix}^{(1,1)}}{\det \begin{pmatrix} 1-x & -x & 0 \\ 0 & 1-x & -x \\ 0 & 0 & 1-x \\ \end{pmatrix}}\\ &=\frac{\det\begin{pmatrix} 1-x & -x \\ 0 & 1-x \\ \end{pmatrix}}{\det \begin{pmatrix} 1-x & -x & 0 \\ 0 & 1-x & -x \\ 0 & 0 & 1-x \\ \end{pmatrix}}\\ &=\frac{(1-x)^2}{(1-x)^3}\\ &=\frac{1}{(1-x)}\\ \end{align*}

\begin{align*} f^G_{12}(x) &= \frac{ (-1)^{1+2}\det((E_m - xA)^{(2,1)})}{\det(E_m-xA)}\\ &=\frac{-1\det\begin{pmatrix} 1-x & -x & 0 \\ 0 & 1-x & -x \\ 0 & 0 & 1-x \\ \end{pmatrix}^{(2,1)}}{\det \begin{pmatrix} 1-x & -x & 0 \\ 0 & 1-x & -x \\ 0 & 0 & 1-x \\ \end{pmatrix}}\\ &=\frac{-1\det\begin{pmatrix} -x & 0 \\ 0 & 1-x \\ \end{pmatrix}}{\det \begin{pmatrix} 1-x & -x & 0 \\ 0 & 1-x & -x \\ 0 & 0 & 1-x \\ \end{pmatrix}}\\ &=\frac{x(1-x)}{(1-x)^3}\\ &=\frac{x}{(1-x)^2}\\ \end{align*}

\begin{align*} f^G_{13}(x) &= \frac{ (-1)^{1+3}\det((E_m - xA)^{(3,1)})}{\det(E_m-xA)}\\ &=\frac{\det\begin{pmatrix} 1-x & -x & 0 \\ 0 & 1-x & -x \\ 0 & 0 & 1-x \\ \end{pmatrix}^{(3,1)}}{\det \begin{pmatrix} 1-x & -x & 0 \\ 0 & 1-x & -x \\ 0 & 0 & 1-x \\ \end{pmatrix}}\\ &=\frac{\det\begin{pmatrix} -x & 0 \\ 1-x & -x \\ \end{pmatrix}}{\det \begin{pmatrix} 1-x & -x & 0 \\ 0 & 1-x & -x \\ 0 & 0 & 1-x \\ \end{pmatrix}}\\ &=\frac{(-x)^2}{(1-x)^3}\\ &=\frac{x^2}{(1-x)^3}\\ \end{align*}

Also: \begin{align*} f(x)&=f^G_{11}+f^G_{12}+f^G_{13}\\ &=\frac{1}{(1-x)}+\frac{x}{(1-x)^2}+\frac{x^2}{(1-x)^3}\\ &=-\frac{1}{(x-1)}-\frac{1}{(x-1)^2}-\frac{1}{(x-1)^3}\\ \end{align*}

Is this right? And how can i solve b)

Thanks in advance

Answer 1

The finite state machine is correct. But note, the entries $a_{i,j}$ of the transition matrix $A=(a_{i,j})_{0\leq i,j\leq 2}$ count the number of possibilities to walk in one step from state $q_i$ to state $q_j$. Since we can go from $q_0$ to $q_0$ either via $a$ or $c$, we have two possibilities and therefore $$a_{1,1}=2$$ The same holds true for $a_{2,2}$ and $a_{3,3}$. The state transition from $q_0$ to $q_1$ and the transition from $q_1$ to $q_2$ is done via $b$, so that $a_{1,2}=a_{2,3}=1$.

We conclude the matrix $A$ is \begin{align*} A= \begin{pmatrix} 2 & 1 & 0 \\ 0 & 2 & 1 \\ 0 & 0 & 2 \\ \end{pmatrix} \end{align*}

Since we consider words containing exactly two $b$'s, all valid words are generated when starting in state $q_0$ and ending in state $q_2$. Therefore we need to calculate only $f_{13}^G$.

Note: This is a difference to the example in OPs question, where both states are end states.

We obtain \begin{align*} f(x)=f^G_{13}(x) =\frac{\det\begin{pmatrix} -x & 0 \\ 1-2x & -x \\ \end{pmatrix}}{\det \begin{pmatrix} 1-2x & -x & 0 \\ 0 & 1-2x & -x \\ 0 & 0 & 1-2x \\ \end{pmatrix}} =\frac{x^2}{(1-2x)^3}\\ \end{align*}

To determine an explicit formula of the coefficients $a_n$ of the generating function $f(x)$ we use the formula of the Binomial series

\begin{align*} \frac{x^2}{(1-2x)^3}&=x^2\sum_{n\geq 0}\binom{-3}{n}(-2x)^n\\ &=x^2\sum_{n\geq 0}\binom{n+2}{n}(2x)^n\tag{1}\\ &=\frac{1}{4}\sum_{n\geq 0}\binom{n+2}{2}(2x)^{n+2}\tag{2}\\ &=\frac{1}{4}\sum_{n\geq 2}\binom{n}{2}(2x)^n\tag{3} \end{align*}

Comment:

• In (1) we use the binomial identity $\binom{-k}{j}=\binom{k+j-1}{j}(-1)^j$

• In (2) we use $\binom{n}{k}=\binom{n}{n-k}$

• In (3) we shift the index $n$ by $2$

We conclude $a_n$, the number of words of length $n\geq 2$ is \begin{align*}a_n=\frac{1}{4}\binom{n}{2}2^n=2^{n-3}n(n-1)\qquad\qquad n\geq 2\tag{4} \end{align*}

Hint: It's often a good idea to verify the problem for small $n$ manually

\begin{align*} S_2=\{&aa\}\\ S_3=\{&aab,aac,aba,aca,baa,caa\}\\ S_4=\{&aabb,abab,abba,baab,baba,bbaa,\\ &aabc,abac,abca,baac,baca,bcaa,\\ &aacb,acab,acba,caab,caba,cbaa,\\ &aacc,acac,acca,caac,caca,ccaa\} \end{align*}

and we see: \begin{align*} |S_2|&=a_2=1\\ |S_3|&=a_3=6\\ |S_4|&=a_4=24\\ \end{align*}

in accordance with the result (4).