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.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more