# Chomsky Classification of Grammars – Tutorial

# Chomsky Classification of Grammars

According to Noam Chomosky, there are four types of grammars – Type 0, Type 1, Type 2, and Type 3. The following table shows how they differ from each other –

Grammar Type | Grammar Accepted | Language Accepted | Automaton |
---|---|---|---|

Type 0 | Unrestricted grammar | Recursively enumerable language | Turing Machine |

Type 1 | Context-sensitive grammar | Context-sensitive language | Linear-bounded automaton |

Type 2 | Context-free grammar | Context-free language | Pushdown automaton |

Type 3 | Regular grammar | Regular language | Finite state automaton |

Take a look at the following illustration. It shows the scope of each type of grammar –

## Type – 3 Grammar

**Type-3 grammars** generate regular languages. Type-3 grammars must have a single non-terminal on the left-hand side and a right-hand side consisting of a single terminal or single terminal followed by a single non-terminal.

The productions must be in the form **X â a or X â aY**

where **X, Y â N** (Non terminal)

and **a â T** (Terminal)

The rule **S â Îµ** is allowed if **S** does not appear on the right side of any rule.

### Example

X â Îµ X â a | aY Y â b

## Type – 2 Grammar

**Type-2 grammars** generate context-free languages.

The productions must be in the form **A â Î³**

where ** A â N** (Non terminal)

and **Î³ â (T âª N)*** (String of terminals and non-terminals).

These languages generated by these grammars are be recognized by a non-deterministic pushdown automaton.

### Example

S â X a X â a X â aX X â abc X â Îµ

## Type – 1 Grammar

**Type-1 grammars** generate context-sensitive languages. The productions must be in the form

**Î± A Î² â Î± Î³ Î²**

where **A â N** (Non-terminal)

and **Î±, Î², Î³ â (T âª N)*** (Strings of terminals and non-terminals)

The strings **Î±** and **Î²** may be empty, but **Î³** must be non-empty.

The rule **S â Îµ** is allowed if S does not appear on the right side of any rule. The languages generated by these grammars are recognized by a linear bounded automaton.

### Example

AB â AbBc A â bcA B â b

## Type – 0 Grammar

**Type-0 grammars** generate recursively enumerable languages. The productions have no restrictions. They are any phase structure grammar including all formal grammars.

They generate the languages that are recognized by a Turing machine.

The productions can be in the form of **Î± â Î²** where **Î±** is a string of terminals and nonterminals with at least one non-terminal and **Î±** cannot be null. **Î²** is a string of terminals and non-terminals.

### Example

S â ACaB Bc â acB CB â DB aD â Db