Chomsky Hierarchy of languages

 Chomsky classified the grammars into four types. They are Type-0, Type-1, Type-2 and Type-3. This is shown in the following diagram

The description of these grammars are given in the following section

1. Type-0 Grammar

Type-0 grammars represents exactly the languages recognized by the Turing Machine. This is also called as unrestricted or phrase-structured grammar. The general structure of this grammar is given below,

where both the left and right hand side of the production may contain any number of terminals and variables.

Example 1.1:  S -> ACaB

                        Bc -> acB

                        CB -> DB

                         aD -> Db

2. Type-1 Grammar

Type-1 grammars denotes the languages recognized by the Linear Bounded Automaton (LBA). The general structure of this grammar is given below,

where the left and right side of the production consists of any number of terminal (T) and non-terminal (V) symbol, but   must contain a non-terminal. That is, the length of the left hand side of the production must be less than or equal to the length of the right side of the production. Also, left hand side of the production must contain a variable.

Example 2.1: AB -> AbBc

                     A -> bcA

                     B -> b

3. Type-2 Grammar

Type-2 grammars represents the languages recognized by the Push Down Automaton(PDA). The general structure of this grammar is given below,

A -> B

where A belongs to V , and B belongs to (V | T )*.  That is, the left hand side of the production must contain a variable while right hand side of the production may contain any number of variables and terminals.

Example 3.1: S -> 0A1 | 1A0

                      A -> 0A1 | 1A0 | 0 | 1

4. Type-3 Grammar

Type-3 grammars represents the languages recognized by the Finite Automaton(FA). The general structure of this grammar is given below,

V -> T; V -> T*V

where V is variable, and T is Terminal. That is, the left hand side of the production must contain a variable while right hand side of the production must either a terminal or a terminal followed by a variable.

Example 4.1: X -> a | aY

                       Y -> b