Right- or Left-Linear Grammar:

Right- or Left-Linear Grammar:
A linear grammar is a grammar in which at most one variable can occur on the
right/left side of any production without restriction on the position of this variable.
Definition (Right-linear):
A grammar G = (V,T, S, P) is said to be right-linear if all productions are of the form:
A ? xB, A ? x,
where A, B?V and x ? T*.
Definition (Left-linear):
A grammar G = (V,T, S, P) is said to be left-linear if all productions are of the form:
A ? Bx,
A ?x,
where A, B ? V and x ? T*.
2. Hierarchy of Grammars(Chomsky Hierarchy):
The Chomsky hierarchy classifies grammars according to syntactic restrictions
on rules as following. Let G = (?, V, S, P) be a grammar.
1. G is called a Type-0 grammar or an unrestricted grammar.
2. G is a Type-1 or context-sensitive grammar.
3. G is a Type-2 or context-free grammar.
4. G is a Type-3 or regular grammar.

2.1 An Unrestricted Grammar:
A set of production rules of the form ? where and are arbitrary strings
of terminal and non-terminal symbols. The rules of these grammars do not have the
restriction above, their left-hand sides may contain any string of terminal and /or nonterminal
symbols, provided there is at least one non-terminal symbol. The type of
automata which can recognize such a language is a Turing machine.