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

Contributor's Info

Created:
0Comment