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.


I'm interested in any ideas. Thanks.


2 Answers 2


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


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.

  • $\begingroup$ How is this the generating function approach? $\endgroup$ Sep 20, 2013 at 2:27
  • $\begingroup$ Well, your approach isn't clear, but one way to get something out of it is along the lines I describe. There could be other ways. $\endgroup$ Sep 20, 2013 at 3:15
  • $\begingroup$ @EnjoysMath To see an example of using linear algebra and eigevalues directly to address the number of accepted words, see my answer on the question Yuval mentioned. Note, that this approach is not that easy to generalize to reducible DFAs without using the generating functions approach. $\endgroup$ Sep 20, 2013 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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