This is of course a special case of the Chomsky-Schutzenberger theorem that unambiguous context-free languages have algebraic generating functions. Restricted to a regular language it is like this. Assume the automata has state set $1,...,n$. Let $1$ be the initial state for convenience. Let A be the adjacency matrix of the automaton, let $e_1$ be the standard unit row vector and let $c$ be the column vector which is the characteristic vector of the terminal states. Then it is easy to see that the generating function is $$f(t)=\sum_{n=0}^{\infty}e_1A^nct^n = e_1\left[\sum_{n=0}^{\infty}A^nt^n\right]c= e_1(I-tA)^{-1}c.$$ Now using the classical adjoint formula for the inverse, you get that the denominator is $\det(I-tA)$ and the numerator is what it is.
|
2 | added 12 characters in body | ||
|
|
||||
|
|
1 |
|
||
|
This is of course a special case of the Chomsky-Schutzenberger theorem that context-free languages have algebraic generating functions. Restricted to a regular language it is like this. Assume the automata has state set $1,...,n$. Let $1$ be the initial state for convenience. Let A be the adjacency matrix of the automaton, let $e_1$ be the standard unit row vector and let $c$ be the column vector which is the characteristic vector of the terminal states. Then it is easy to see that the generating function is $$f(t)=\sum_{n=0}^{\infty}e_1A^nct^n = e_1\left[\sum_{n=0}^{\infty}A^nt^n\right]c= e_1(I-tA)^{-1}c.$$ Now using the classical adjoint formula for the inverse, you get that the denominator is $\det(I-tA)$ and the numerator is what it is. |
||||
