Has anyone mixed linear algebra with formal language theory in this way?

Question

Let $G$ be the grammar: $$ S \rightarrow aAb \\ A \rightarrow aA + a + \epsilon $$

where $\epsilon$ is the empty string, $a,b$ are terminals and $S,A$ non-terminals with $S$ the start symbol. Consider vectors of grammar rule RHS's, for instance the basic one $\nu = \begin{pmatrix} S\\A\\a\\b\\\epsilon\end{pmatrix}$. Then $\nu$ is an eigenvector of some matrix that transforms vectors of grammar rule RHS's into the same.

Let $T = \begin{pmatrix} 0 & 0 & 0 & aA & 0\\ 0 & a & \epsilon & 0 & \epsilon \\ 0 & 0 & \epsilon & 0 & 0 \\ 0 & 0 & 0 & \epsilon & 0 \\ 0 & 0 & 0 & 0 & \epsilon \end{pmatrix} $

Then if we let $0$ represent the empty set and concatenation by it equals $0$, then $\nu \rightarrow T\nu$ is an eigenvector with eigenvalue $\epsilon$.

Unrelated, but a regular language is represented by $T$ with only terminals and $\epsilon$ in the matrix.

Edit

I'm interested in any ideas. Thanks.

Answer 1

How you choose your vector $\nu$ for every terminal symbol you must have a row with exactly one $\epsilon$ in your matrix so that it is a fixed point. So we could disregard terminal symbols, and what you get then seems to be similar to how grammars could be read as language equations, which could be generalized to equations between formal power series. This goes back to Schützenberger, Conway and others from the 60's, but the fact that grammars could be read as language equations is somehow folklore I guess.

To be more specific, given a context free grammar $G = (N, T, S, P)$ we consider the non-terminals $N$ as variables, and to every rule we associate a language equation. For example the rule $A \to B + bC + c$ corresponds to the equation $$ A = B \cup \{b\}\cdot C \cup \{c\} $$ where $A,B,C$ are variables for languages. In your example we have \begin{align*} S = \{a\}A \{b\} \\ A = \{a\}A \cup \{a\} \cup \{\epsilon\}. \end{align*}

If we can give these equations in matrix form, such that the matrix just contains terminals, then the described language is regular. This is usually shown by building an automaton of such right (or left) linear grammars. But could also be shown with this algebraic approach, for if $\vec X = M \vec X + \vec b$ where $\vec X$ is the vector of all non-terminals and $M$ a matrix with entries from $T \cup \{\epsilon\}$ (or more generally regular languages) and similar for entries for $\vec b$, then (this is Arden's rule, which could be lifted to matrices by suitable generalisations) $\vec X = M^{\ast}\vec b$ and $M^{\ast}\vec b$ just contains regular languages in every entry.

Somehow surprisingly, due to Conway from his book Regular algebra and finite machines this could be taken further, giving an elegant proof of Gruskas theorem characterising linear grammars (your example is a linear grammar). If we define $L_x, R_x : T^{\ast} \to T^{\ast}$ by $L_x(w) = xw, R_x(w) = wx$ for $x \in T$ and their usual extension to languages. Then every linear grammar could be written as $\vec X = M \vec X + \vec b$, where this time the matrix $M$ has operators $R_a, L_a$ or $\emptyset$ as operator, where $\emptyset$ means the operators $\emptyset(L) = \emptyset$, as entries.Also $\epsilon$ the operator $\epsilon(L) = \{\epsilon\}$ and similar for the terminal symbols as constant operators and $+$ of operators is the union of their images. For your example $$ \begin{pmatrix} S \\ A \end{pmatrix} = \begin{pmatrix} \emptyset & R_bL_a \\ \emptyset & L_a \end{pmatrix} \begin{pmatrix} S \\ A \end{pmatrix} + \begin{pmatrix} \emptyset \\ a + \epsilon \end{pmatrix}. $$ Now we could built up an regular algebra, but instead of alphabet symbols we use the operators $R_x, L_x, \emptyset, \epsilon, x$ with $x \in T$, hence such an equation above also has a solution $\vec X = M^{\ast}\vec b$, but this time every element form $\vec X$ is an operator, but putting $\epsilon$ as argument gives us a word from the grammar, i.e. $S = S(\epsilon)$.

Answer 2

The approach you're describing is the generating function approach. By solving systems of polynomial equations, one can calculate the number of words of given length (generated by any non-terminal), and through it the corresponding asymptotics.

For regular languages one can directly use linear algebra to estimate the number of words of given length. The result is described in the Wikipedia article as well as here; see also this question.