What is Grammar

Grammar is a finite set of rules for generating syntactically correct sentences or meaningful correct sentences. These rules are called Productions.
Each production rule is composed of two elements one is Variables and the other is Terminals.

  • Variables are the symbols that are used to generate the sentences, but not the part of the sentences. Variables are represented by capital letters. Variables are also known as Non-Terminals.
  • Terminals are the symbols that are the components of the sentences generated by the given grammar. Terminals are represented by small letters.
  • Productions are the rules of Grammar that specify the substitution of variables. Productions are in the form of α→β. 
    where α is a Non-Terminal and β is a Terminal

Formal definition of Grammar

Generally, Grammar G is represented by four tuples. G = (V, T, P, S)

Example:

Consider a Grammar G = (V, T, P, S)
V = {S, A, B}  #set of variables
T = {a, b} #set of terminals
P = {
S→AB
A→a
B→b
}  #set of production rules
S = {S} #Start Symbol

Types Of Grammar

According to Chomsky, there are four types of Grammar.

Type-0 Grammar

All the productions are in the form of α→β
Where, α∈V+T+
            β∈V+T*

Epsilon is not allowed in α

Type-1 Grammar

All the productions are in the form of α→β
Where, α∈V+T+
            β∈V+T+
and      α≤β

Epsilon is allowed neither in α nor in β and length of α must be less than or equal to β

Type-2 Grammar

All the productions are in the form of α→β
Where, α∈V
            β∈V+T*
and      α=1

Length of α must be 1.

Type-3 Grammar

All the productions are in the form of α→β
Where, α∈V
            β∈VT* or T*   (Left Linear Grammar)
              ∈T* or T*V   ( Right Linear Grammar)
and     α=1

Length of α must be 1. A grammar can only be Left Linear Grammar or Right Linear Grammar. Any type-3 grammar cannot be both LLG and RLG.

Note: Chomsky Hierarchy only works for grammar with no null production.

Chomsky HierarchyTypes of Grammar