**As per **Chomsky classification, there are three types of grammar:

**Type 0**, **Type 1**, **Type 2 and Type 3**.

**Type 0**: This grammar is called **Phrase Structure Grammar (PSG) **or **Unrestricted Grammar**; it is called unrestricted because it is the highest degree of grammar with no restriction.

__General definition of Type 0 grammar:__

**[left-hand side of the production can contain variables (non-terminal) and terminals but not empty symbols (λ) and right-hand side of the production can contain variables and terminals including empty symbols (λ)]**

**Examples: **

S → Aba | λ

aS → aAb

AB → CB

**Language:** Language of this grammar is **Recursively Enumerable Language**.

**Machine: ****Turing Machine**.

**Type 1**: This grammar is called **non-contracting grammar**** **or **Context Sensitive Grammar**.

__Definition of Context Sensitive Grammar:__

**G** = (V, T, S, P)

**V** is a finite set of symbols called the variables (Non-terminals);

**T** is the set of terminal symbols;

**S ∊ **V is a designated symbol called the start symbol;

**P:** **αAβ → αγβ**, with A ∊ V (Non-terminals), $\gamma \in {(V\cup T)}^{+},\alpha ,\beta \in {(V\cup T)}^{*}$ or S → λ,

And if S → λ ∊ P, then S does not appear on the right-hand side of any production.

**Examples:**

S → cD

aA → aBb

SA → CB

**Language: **Language of this grammar is **Context Sensitive Language**.

**Machine: **Language of this grammar is **Linear Bounded Automata**.

**Type 2**: This grammar is called **Context Free Grammar**.

__Definition of Context Free Grammar:__

**G** = (V, T, S, P)

**V** is a finite set of symbols called the variables (Non-terminals);

**T** is the set of terminal symbols;

**S ∊ **V is a designated symbol called the start symbol;

**P:** **V → (V ∪ T)* **[Right hand side of the production V has no left or right context]

Let **αAβ** is string here **α **is left context and **β** is right context. λAλ, here no left and right context.

(λ.A = A.λ = A).

This grammar is called **context free grammar** because Right hand side of the production V has left or right context-free.

**Examples:**

S → cD | λ

A → aBb

B → CB

**Language**: **Context Free Language**

**Machine**: **Pushdown Automata (PDA) **

**Note:** This is very important grammar for us because generally, we are working with context-free grammar.

**Type 3**: This grammar is called **Regular grammar **or** ****Finite State Grammar.**

__Definition of Regular Grammar:__

**G** = (V, T, S, P)

**V** is a finite set of symbols called the variables (Non-terminals);

**T** is the set of terminal symbols;

**S ∊ **V is a designated symbol called the start symbol;

**P:** **V → T*|T*V (Right linear)**

** V → T*|VT* (Left linear) **

We can write this product more simple way like **V → T* or V → T*V or V → VT*.**

**A Regular grammar is one that is either right linear or left linear but not both.**

**Note:** **What is Linear:**** ax + b **is linear but $a{x}^{2}+bx+c$ is non-linear because it has the power of x (variable). xy + 6 = 0 is non-linear because it has two variables, linear means only one variable will be there (Single).

**Examples:**

S → a | λ

A → aA ( right linear)

C → Caa (left linear)

B → abba

**Language: ****Regular Language or Finite State Language**

**Machine: ****Finite Automata**