Type of Grammar | TOC

Type of Grammar

1. Type 0 ( Unrestricted grammar) 

2. Type 1 (Context sensitive grammar / CSG)

3. Type 2 (Context Free Grammar / CFG)

4. Type 3 (Regular Grammar)

1. Type 0 (Unrestricted grammar):

Type 0 grammar is a set of four tuples 

    ( V, T, P, S)

V  is a set of variables

T is set terminals

S is starting symbol

P is a set production 

Type0 is represented as  

α→β

- α contains at least one symbol. Null can be left hand side.

- α - (VUT)*

- β - (VUT)*

- α contain at least one variable.

- |α| <=|β|  or length(α) <=length(β)

Example: 

S → aSBC | aBC

CB → BC

aB → ab

bB → bb

bc → bc

cc → CC

2. Type 1 (Context sensitive grammar / CSG)

Type 1 grammar is a set of four tuples 

    ( V, T, P, S)

V  is a set of variables

T is set terminals

S is starting symbol

P is a set production 

Type1 is represented as   

α1 A α2 → α1 β α2

 where:

A ∈ V

α1,α2  ∈ (VUT)*

β ∈ (VUT)*

        length of |L.H.S| <= length of |R.H.S|

Note:

Here one thing is noted down that starting and ending symbol of Type1 Grammar are same such as it start with α1 and end with α2.

Example: 

1. aB → ab  is in type 1

    where: α1=a , α2 = ε

2. abBd → abb  Not in CSG

    where:  α1=ab , α2 = is not same

3. BC → CB  Not in CSG

    here only one variable is used  but here there are two variable.

4. A → ab  is in CSG

    where:   α1=ε , α2 = ε , β=ab

5. A → ε

    where:α1= ε , α2 = ε , β= ε

Note: 

  - Starting and ending symbol will be same in any production of this Grammar .

  - Every context sensitive grammar is type 0 but reverse is not necessary.

3. Type 2 (Context Free Grammar / CFG)

Type 2 grammar is a set of four tuples 

    ( V, T, P, S)

V  is a set of variables

T is set terminals

S is starting symbol

P is a set production 

Type2 is represented as  

    A → α

where:

     A ∈ V

    α ∈ (VUT)*

Example:  

    A → ab  is in CFG

    

Note:

- Every context free grammar is type1and type0 but the reverse is not necessary true.

- Grammar which does not depends on context is CFG.

4. Type 3 (Regular Grammar):

Regular grammar are of type type:

i) Left linear regular grammar.

ii) Right linear regular grammar.

i) Left linear regular grammar.

It is a set of four tuples 

    ( V, T, P, S)

V  is a set of variables

T is set terminals

S is starting symbol

P is a set production 

It is represented as  

      A → Bα   or   A → α

where:

    A ∈ V , B ∈ V , α ∈ T*

Example:

     S → S10 | 10

     A → A0 |1

ii) Right linear regular grammar:

It is a set of four tuples 

    ( V, T, P, S)

V  is a set of variables

T is set terminals

S is starting symbols

P is a set production of form  

    A →  α B   OR   A →  α 

where:

    A ∈ V  , B ∈ V ,  α ∈ T*

Example:

     S → 10S | 10

     A → 0A |1

Note:

Every Regular Grammar is Type 0, Type 1 and Type 2 but reverse is not necessary true. 

Note : As we go for downward the restriction will increased.

This hierarchy is called Chomsky hierarchy and this hierarchy of Grammar is called Chomsky hierarchy Grammar.