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

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.

Here,

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

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

α, β ε (V ∪ T)*.