Regular grammars are another way to describe regular languages.
Recall that a grammar is made of of terminals, variables, and
production rule.
As the name implies, a regular grammar is a special type of
grammar (we will see plenty of grammars later that are not regular).
Which begs the question: What makes a grammar regular?
Before we can properly answer that, we need some definitions.
Suppose we have the following Grammar \(G = (V, T, S, P)\) where,
\[\begin{split}\begin{array}{lll}
& & \mbox{represented by} \\
V & \mbox{variables (nonterminals)} & A,B,..,Z (that is, capital letters)\\
T & \mbox{terminals} & a,b,..,z,0,1,...9 (lower case letters and numbers)\\
S & \mbox{start symbol} \\
P & \mbox{productions (rules)}\\
\end{array}\end{split}\]
\(V\), \(T\), and \(P\) are finite sets.
Linear grammar:
A grammar is linear if has a single variable
in the RHS of every production rule.
\[\begin{split}\begin{array}{c}
\mbox{All productions are of the form} \\
A \rightarrow xB \\
A \rightarrow Cx \\
A \rightarrow x \\
\mbox{where}\ A,B,C \in V, x \in T^*
\end{array}\end{split}\]
In this grammar, each production rule has at most one variable on the
RHS.
(Note: It does not need to be the same terminal \(x\) in every production!)
Right-linear grammar: This is a special case of linear
grammar.
If a grammar is linear and any variable, if it exists, always occurs at
the right end of the RHS, then the grammar is called a Right-linear grammar.
For example, the grammar:
\[\begin{split}\begin{array}{c}
A \rightarrow xB \\
A \rightarrow xC \\
A \rightarrow y \\
\mbox{where}\ A,B,C \in V, x,y \in T^*
\end{array}\end{split}\]
Note: \(x\) or \(y\) is a string of length 0 or more.
Each production has at most one variable, so the grammar is linear.
The variables (B and C) are at the end of the RHS,
so it is a right linear grammar.
Left-linear grammar: This is the same as Right-linear grammar,
but the occurance of any variable, if it exists, is at the begining of each
production RHS.
For example,
\[\begin{split}\begin{array}{c}
A \rightarrow Bx \\
A \rightarrow Cy \\
A \rightarrow x \\
\mbox{where}\ A,B,C \in V, x,y \in T^*
\end{array}\end{split}\]
Each production has at most one variable, so the grammar is linear.
The variables (B and C) are at the start of the RHS,
so it is a left linear grammar.
OK, so now we have the definitions that we need to define a regular
grammar.
