Chomsky Hierarchy of Language

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