Right-Linear Grammar
A grammar is right-linear, if all productions have one of the two forms:
V ? T* V or
V ? T*
We can have only one variable-symbol on the left-hand side and on the right-hand side, we have at most one variable, and this is at the far right.
Left-Linear Grammar
A grammar is left-linear, if all productions have one of the two forms:
V ? V T* or
V ? T*
We can have only one variable-symbol on the left-hand side and on the right-hand side, we have at most one variable, and this is at the far left.
Regular Grammar
A grammar is regular, if it is either right-linear or left-linear.
This means, all productions in the grammar have to be completely left-linear or completely right-linear but not mixed left-linear and right-linear.
Linear Grammar
Grammars, in which each rule is in right-linear or left-linear form, i.e. left-linear and right-linear rules can be mixed, is called linear.
Linear grammars are a more general class of grammars than regular grammars.
Example
The grammar with the following productions:
S ? a X
X ? S b
S ? ?
is linear but neither right-linear nor left-linear, and thus not a regular grammar.
Which language does this grammar describe? H.W
Example – Grammars
What languages do the following grammars generate? H.W
G1 = (V, T, P1, S) with V = {A, B} T = {a, b} and Productions P1 :
S ? A | B
A ? a A | a
B ? b B | b
G2 = (V, T, P2, S) with V, T as above and Productions P2 :
S ? A
A ? a A | B | ?
B ? b B | ?