Chomsky Hierarchy of Language

Chomsky Hierarchy

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.

Chomsky Hierarchy
Chomsky Hierarchy

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)
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)
V -> T*V /T* (extended right-regular grammar)

For example : 

S -> ab

Leave a Reply 0

Your email address will not be published. Required fields are marked *