<p>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.</p>

<p>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*}</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Arden%27s_Rule" rel="noreferrer">Arden's rule</a>, 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.</p>

<p>Somehow surprisingly, due to Conway from his book <em>Regular algebra and finite machines</em> this could be taken further, giving an elegant proof of Gruskas theorem characterising <a href="https://en.wikipedia.org/wiki/Linear_grammar" rel="noreferrer">linear grammars</a> (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 &amp; R_bL_a \\ 
  \emptyset &amp; 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)$.</p>

CC BY-SA 4.0
2018-05-30T12:46:46.170Z
2018-05-30T13:00:38.160Z
2018-05-30T13:00:38.160Z
StefanH
<p>The approach you're describing is the <em>generating function</em> 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.</p>

<p>For regular languages one can directly use linear algebra to estimate the number of words of given length. The result is described in the <a href="http://en.wikipedia.org/wiki/Regular_language#The_number_of_words_in_a_regular_language" rel="nofollow noreferrer">Wikipedia article</a> as well as <a href="https://cs.stackexchange.com/questions/1039/number-of-words-in-the-regular-language-00">here</a>; see also <a href="https://cs.stackexchange.com/questions/11350/asymptotics-of-the-number-of-words-in-a-regular-language-of-given-length">this question</a>.</p>

CC BY-SA 3.0
2013-09-20T02:27:55.637Z
How is this the generating function approach?
Daniel Donnelly
CC BY-SA 3.0
2013-09-20T03:15:53.777Z
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.
Yuval Filmus
CC BY-SA 3.0
2013-09-20T19:51:55.480Z
@EnjoysMath To see an example of using linear algebra and eigevalues directly to address the number of accepted words, see [my answer](http://cs.stackexchange.com/a/1048/55) on the question Yuval mentioned. Note, that this approach is [not that easy to generalize to reducible DFAs](http://cs.stackexchange.com/a/11333/55) without using the [generating functions approach](http://cs.stackexchange.com/a/1049/55).
Artem Kaznatcheev
CC BY-SA 3.0
2013-09-20T02:17:01.330Z
2013-09-20T02:17:01.330Z
2017-04-13T12:48:30.830Z
Yuval Filmus
<p>Let $G$ be the grammar:
$$
S \rightarrow aAb \\
A \rightarrow aA + a + \epsilon
$$</p>

<p>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. </p>

<p>Let $T = 
\begin{pmatrix} 
0 &amp; 0 &amp; 0 &amp; aA &amp; 0\\ 
0 &amp; a &amp; \epsilon &amp; 0 &amp; \epsilon \\
0 &amp; 0 &amp; \epsilon &amp; 0 &amp; 0 \\
0 &amp; 0  &amp; 0 &amp; \epsilon &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; \epsilon
\end{pmatrix} $</p>

<p>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$.</p>

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

<h2>Edit</h2>

<p>I'm interested in any ideas.  Thanks.</p>

<fl.formal-languages><linear-algebra><grammars>
Has anyone mixed linear algebra with formal language theory in this way?
Daniel Donnelly
# Has anyone mixed linear algebra with formal language theory in this way?

(Asked by: username_0 on 2013-09-19)

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.

**Tags:** fl.formal-languages, linear-algebra, grammars

---

## 2 answers

### Answer by username_1 on 2018-05-30. Score: 5 | Accepted answer

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](https://en.wikipedia.org/wiki/Arden%27s_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](https://en.wikipedia.org/wiki/Linear_grammar) (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 by username_2 on 2013-09-20. Score: 10

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](http://en.wikipedia.org/wiki/Regular_language#The_number_of_words_in_a_regular_language) as well as [here](https://cs.stackexchange.com/questions/1039/number-of-words-in-the-regular-language-00); see also [this question](https://cs.stackexchange.com/questions/11350/asymptotics-of-the-number-of-words-in-a-regular-language-of-given-length).

> **Comments:**
> **username_0**: How is this the generating function approach?  
> **username_2**: 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.  
> **username_3**: @EnjoysMath To see an example of using linear algebra and eigevalues directly to address the number of accepted words, see [my answer](http://cs.stackexchange.com/a/1048/55) on the question Yuval mentioned. Note, that this approach is [not that easy to generalize to reducible DFAs](http://cs.stackexchange.com/a/11333/55) without using the [generating functions approach](http://cs.stackexchange.com/a/1049/55).  

---

