Grammar & Types of Grammar

Grammar:

A Grammar is described by four tuples - ( V_N  ,  ∑ ,  P,  S ) 

Where,

            V_N = Finite non empty set of variables

         ∑ =Finite non empty set of terminals (or input alphabets)

         P = Production rules ( X  -> Y where X and Y are the combination of              variable and terminals)

         S = Starting symbol

Note : Variables are represented in capital letters (like A,B,C,D,S,.... etc)

          Terminals are represented by small letters or numbers (like a,b,c..0,1,2...etc)

Classification of Grammar:

This Classification is based on format of production rules-

1) Type 0 grammar: (Grammar with no restriction)

•  It is also called phase structured grammar.
•  This type of grammar is accepted by Turing Machine(TM).

       
2) Type 1 grammar: (Context Sensitive Grammar)

•  it is also called context dependent grammar.
•  Productions are in the form of α  A  β  ->  α B β, where α and  β are  called left context and right context of the grammar respectively.
•  This type of grammar is accepted by Linear bounded automata (LBA).

3) Type 2 grammar: (Context free grammar)

• Productions are in the form A -> α,where α belongs to (V_N  U ∑ )^*

means that left side of the arrow contains only one variable and right side of the arrow contains combination of variables and input terminals including null.

• This type of grammar is accepted by Push down automata (PDA).

4) Type 3 grammar: ( Regular Grammar)

• Productions are in the form of A -> aB   or  A -> a, where A, B are variables and a is terminal. (Left side of the production contains only one variable and right side of the production contains only one terminal or combination of one terminal and one variable (like aB).
• This type of grammar is accepted by Deterministic finite automata (DFA).

Relation between all grammars: 

type 3 <= type 2 <= type 1 <= type 0

Numericals :

Consider the following grammars-

1.    S -> ABa                   2.   S -> aS | aA         

       A -> aA | a                      A -> aA | a                          

       B -> b                                                             

                                                                             

check whether the above grammar is type 0, type 1 , type 2 or type 3 ?

Solution:

First grammar is Type 2 grammar because in this grammar, the left side of the arrow contains only one variable and right side of the arrow contains the combination of variables and terminals. 

Second grammar is type 3 Grammar because in this grammar, the left side of the arrow contains only one variable and right side of the arrow contains only one terminal or combination of one terminal and one variable.