What does the word Regular or Linear mean with respect to formal grammars? I'm currently studying formal languages and automata.  We have covered the subjects of regular grammars and expressions, and right/left linear grammars.  I've been searching Google for a while now, but I can't seem to find a simple answer to the question of why they are called Regular or Linear.  I have found an abundance of explanations on how to identify if a grammar/language is regular or right/left linear, but that's not my question.  From what I have found Linear is in reference to the algorithmic parsing time of the grammar, O(n).  However, this is just my assumption, and I haven't found anything that definitively says this is so.  
So, if anyone can please explain this and provided a link to a source it would be greatly appreciated.
Thanks 
 A: You are actually asking two interesting questions.
The term regular is an overloaded one in mathematics (think of regular element, regular semigroup,  regular space, regular scheme, regular conditional probablity, just to name a few), but in computer science, it mainly refers to regular expressions and regular languages, introduced by Kleene [1] in 1951.
The term linear refers to linear equations, but in a noncommutative context. Consider for instance
the right-linear grammar
\begin{align}
S_1 &\to aS_2 + 1\\
S_2 &\to bS_1 
\end{align}
It can be interpreted as a system of linear equations over the semiring $\mathcal{P}(A^*)$ of languages on the alphabet $A$. A solution of this linear system is a pair of languages $(L_1, L_2)$ satisfying $L_1 = aL_2 + 1$ and $L_2 = bL_1$ (here $+$ stands for union and $1$ is the language reduced to the empty word). In this case, the unique solution is $\bigl((ab)^*, b(ab)^*\bigr)$. 
[1] Kleene, Stephen C. (1951). Shannon, Claude E.; McCarthy, John (eds.). Representation of Events in Nerve Nets and Finite Automata. Automata Studies. Princeton University Press. pp. 3–42.
