Is there any useful connection between formal grammars and linear algebra?
Apologies if this is a silly question, my linear algebra is rusty and my knowledge of grammars is only that required for an undergrad compilers course.
In Aho and Ullman's "Theory of Compiling" book, the authors use a very suggestive notation in chapter 2.2, where they discuss finding regular expressions that satisfy some set of equations. They even note that the algorithm to solve such set of equations is "reminiscent of solving linear equations using Gaussian elimination".
Another thing that feels vaguely similar is this concept of "generation". In the same way that vector spaces are generated from some basis, and the behavior of a linear transformation is determined by how it acts on the basis, a "nice" language is generated by some finite list of production rules, and once a set of production rules are found we can presumably tell a fair bit about the language it generates.
An immediate flaw that comes to mind with the above analogy is how "useless" generators are handled in linear algebra vs. formal grammars. Recall that if we have a generating set for a vector space, we have "useless" vectors that we can trim away to eventually find a linearly independent basis for that space. To my understanding, there is an analogous process to trim useless rules from a grammar that preserves the language it generates. However, if we have a context free grammar for a regular language, it isn't clear to me that there is a generic way to turn that context free grammar into a simpler regular grammar, which means that the amount of simplification we can do is limited if thats correct.
Is there anything deeper here? Or am I grasping for straws and any similarities are superficial?