Thread by @DavidBindel

Because I spent a lot of time going from points A to points B over the past week, and not all of that time was spent listening to podcasts, I present you with Lunchtime Thoughts on Eigenvalues and Regular Languages: a Thread.

A regular language is a set of strings over some finite alphabet that we know how to recognize with a deterministic finite automata. One usually draws a graph for the automata, with symbols on each edge and special start/accept states. But there are other representations.

For example: suppose we write s for a vector of start states, f for a vector of final states, and A(a) for the transitions on symbol a (i.e. A(a)_{ij} = 1 if there is an a-edge from j to i, 0 otherwise).

Then a string a_1, a_2, ..., a_n is in the language if f^T A(a_n) ... A(a_2) A(a_1) s = 1 -- zero otherwise.

(The fact that the automata is deterministic means that the only possible values for this expression are zero or one.)

We will also use A to denote the sum of the A(a) over the full alphabet -- that is, A_{ij} = 1 if there is a transition from state j to state i with any label, and 0 otherwise.

Actually, A_{ij} = # of symbols associated with a given transition -- could be more than one.

Given this formalism, we get some tools for exploring questions about regular languages, like:

a. How many strings are there of length n? Length <= n?

b. How often does any given symbol appear in strings of length <= n?

The first question (number of strings up to some length) is one that I've known about for a long time, and sometimes use when I teach eigenvalue stuff.

Each string is associated with a unique path through the automata. Let u_n(i) denote the number of paths of length n from the start state(s) that terminate at state i; then u_j(0) = s_j, and afterward, u_j(n) = sum_{j -> i} u_j(n+1) = [A u(n)]_j.

The number of accepted strings of length n is therefore

f^T u(n) = f^T A^n s

and one can get an upper bound on the number of such strings in terms of the largest eigenvalue of A (the Perron eigenvalue).

What about the number of strings less than length n? For that we have

f^T (sum_{j=1}^n A^j) s =
f^T (I-A^{n+1}) (I-A)^{-1} s

under the assumption that one is not an eigenvalue of A. Of course, sometimes one is an eigenvalue of A!

When A has an eigenvalue at 1, one essentially has to treat the associated invariant subspace separately. Within that subspace, there can be various Jordan blocks; for each one, the relevant sums end up being polynomial in n.

The more interesting question, at least for staring-into-space-while-commuting me, is the number of times a particular symbol occurs over all strings of a given length.

To get a handle on this, we write a recurrence for

v_j(n) =
# paths of length n ending at j +
# times symbol a appears on them

The recurrence, in matrix form, looks like

v(n+1) = (A + A(a)) v(n)

Hence, the number of times that the symbol a occurs in strings of length n is

f^T (A+A(a))^n s - f^T A^n s.

If we care about strings of length <= n, we again get a geometric series, which is easy except for a little dance around eigenvalue 1.

What I'm left with for the next time I have a long drive: is it possible to do these calculations with a non-deterministic finite automata? The difficulty with an NFA is that strings in the language can now correspond to more than one path through the graph.

But! The number of paths in an NFA corresponding to a given string is easy to write in linear algebra terms -- it is just

f^T A(a_n) .. A(a_2) A(a_1) s

So one could potentially correct for duplicate counts.

Of course, I'm sure that there is a way to do the NFA to DFA conversion that I learned in intro compilers class in purely linear algebra terms, but since I'm just asking for counts -- not actual recognition -- I hope that there's a simpler trick.

I also think it would be absolutely delightful to think about analytically "collapsing" the problem to get a recurrence relation on a smaller state space, but depending on counts at more than one previous step.

In this case, I can again think about everything in terms of a linear time invariant system. But since the history goes back more than one time step, the right analytical tool is not an ordinary eigenvalue problem, but a nonlinear eigenvalue problem (polynomial, really).