Classification Of Grammer
Acc to chomsky grammer are classified into four type:
1) Type-3 Grammer:
A--->αB/β
A,B ∈ V
α,β ∈ T*
This is also called as right linear grammer(RLG).
A--->Bα/β
A,B ∈ V
α,β ∈ T*
This is also called as left linear grammer(LLG).
V=variable
T=terminals
NOTE:- Whatever language is generated by type-3 grammer they are nothing but regular grammer.
2) Type-2 Grammer:(Context Free Grammer)
A--->α ,A ∈ V
α ∈(V ∪ T)*
If a grammer is regular then it is definetly context free but if a grammer is context free then it may not be regular.
e.g
anbmcn+m/n,m>=1
Sol:
S--->aSc/aAc
A--->bAc/bc
3)Type-1 Grammer:(Context sensitive grammer)
x--->y
where x,y ∈ (V ∪ T)+
and |x|=<|y|
this mean always the grammer is non contracting.
e.g:-
S--->abc/aAbc
Ab--->bA
Ac--->Bbcc
bB--->Bb
aB--->aa/aaA
laguage generating by this CSG is?
Sol:
anbncn n>=1
4) Type-0 Grammer:( unrestricted Grammer)
A grammer is called unrestricted if all the production are of the form u--->v where u is in (v ∪ T)+
v is in (v ∪ T)*
v is a varible and T is a terminal