**Chomsky Hierarchy of Language**

According to Chomsky Hierarchy, language is classified as follows:

Type 0 – Unrestricted grammar.

Type 1 – Context-sensitive grammar.

Type 2 – Context-free grammar.

Type 3 – Regular Grammar.

**Type 0:**

- All formal grammars fall under type-0 grammars.
- The Turing machine can detect languages with type 0 grammar.
- The Recursively Enumerable languages are another name for these languages.

Type 0 Language Production in the form of α (alpha) to β (beta) where

**α is ( V + T)* V ( V + T)***- V = Variables
- T = Terminals.

**β is ( V + T )*.**

In type 0 there must be at least one variable on the Left side of production.

**For example: **

Sab -> ba

A -> S

Here, A, S are Variables

and a, b are Terminals

**Type 1:**

- It is also known as Context Sensitive Language.
- It is recognized by the Linear Bound Automata.

According to the following rules, context-sensitive grammar:

- It should be Type 0
- Multiple symbols may be present on the left side of the production rules for the context-sensitive grammar.
- The number of symbols on the left side cannot be more than the number of symbols on the right side.
- The rule of the form A → ε is not allowed unless A is a start symbol. It does not occur on the right-hand side of any rule.
- In type 1, Production is in the form of
**|α**| <=**|β**| Where the count of symbol in**α**is less than or equal to**β**. - Also β ∈ (V + T)+ i.e. β can not be ε

**For Example:**

S -> AB

AB -> abc

B -> b

**Type 2:**

- It should be Type 1
- It is Context-Free Grammar (CFG)
- It is recognized by a Pushdown automata
- The left-hand side of production can have only one variable and there is no restriction on β (right side)
- The production rule is of the form |
**α**| = 1.

**For example:**

S -> AB

A -> a

B -> b

**Type 3:**

- It should be Type 2
- It is a Regular Grammar
- It can be accepted by a finite-state automaton.
- It is the most restricted form of grammar.
- It can be described using regular expressions.
- These languages can be modelled by NFA or DFA.

It should be in the given form only :

V -> VT / T (left-regular grammar)

(or)

V -> TV /T (right-regular grammar)

**For example:**

S -> a

The above form is called strictly regular grammar.

There is another form of regular grammar called extended regular grammar. In this form:

V -> VT* / T* (extended left-regular grammar)

(or)

V -> T*V /T* (extended right-regular grammar)

**For example : **

S -> ab

#cfg #chomsky hierarchy #context free grammar #context sensitive grammar #push-down automata #turing maching #type 0 #type 1 #type 2 #type 3