Explain with an example the Chomsky hierarchy.

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: May 2015


Chomsky hierarchy:

The Chomsky hierarchy classifies the formal language in the four types:

  1. Type 0: Unrestricted grammar

  2. Type 1: Restricted grammar (Context-sensitive)

  3. Type 2: Context free grammar

  4. Type 3: Regular grammar

enter image description here

The formal languages take the form of productions, like α → β

Fig 1. Chomsky hierarchy

Fig 1 describes the set inclusions as described by Chomsky hierarchy. For instance all regular languages are context-free languages but vice versa is not true.

1. Type 0 grammar:

There are no restrictions to define the productions. The languages generated by these grammars are known as recursively enumerable. These languages are recognised by Turing machine. These are of the form: α → β.

2. Type 1 grammar:

These grammars generate context-sensitive languages. These are of the form: α → β, with the following condition |β| >=|α|,i.e. length of β is greater then length of α.

3. Type 2 grammar:

These grammars generate context-free languages. The productions are of the form A → α. Here α ⊆ (V ∪ T)*. Here α represents a sentinel form.

4. Type 3 grammar:

These grammars generate regular languages. These could be of the form A → α or A → αB.


T = Terminals (a,b,......)

V = Variables (A,B,...)

α, β ε (V ∪ T)*.

Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.


Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More