L10 Regular Grammar

• 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 1 : 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.