left linear grammar and right

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 =

is said to be right-linear if all productions are of the form:
A ? xB, A ? x,
where A, B?V and x ? T*.

Left-linear grammar

A grammar G is said to be left-linear if all productions are of the form:
A ? Bx,
A ?x,
where A, B ? V and x ? T*.
Example 1:
Find L)G)
where G =
({S, S1, S2}, {a, b}, S, P)
with
S ? S1ab,
S1?S1ab | S2,
S2 ? a.
Answer. This is a left-linear grammar.
S ? S1ab ? S1abab ? S2abab ?aabab.
Then
L(G) = {aabw |w ? (ab)*}.
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.