# Chomsky Hierarchy

In this article, we have defined and explained **Chomsky Hierarchy** which orders the different languages in Theory of Computation. It is also known as Chomsky Schutzenberger Hierarchy.

Table of contents:

- Chomsky Hierarchy
- Meaning of Chomsky Hierarchy
- Modified / Complete Chomsky Hierarchy

Let us get started with Chomsky Hierarchy.

# Chomsky Hierarchy

This table gives you the idea of the different Languages in Theory of Computation and the position of Context Sensitive Language:

Type | Language | Automata Machine | Power |
---|---|---|---|

Type 0 | Recursively Enumerable | Turing Machine | Strongest |

Type 1 | Context Sensitive | Linear Bounded Automaton | Stronger |

Type 2 | Context Free | Pushdown Automaton | Strong |

Type 3 | Regular | Finite State Automaton | Weak |

The above table is known as Chomsky Hierarchy and was first formed in 1956 by Noam Chomsky. It was presented in a paper titled "On Certain Formal Properties of Grammars, Information and Control" in 1959.

The table is also named as "**Chomsky Schutzenberger Hierarchy**" in honor of another Computer Scientist named Marcel Paul Schutzenberger who played a major role in development of Theory of Computation.

# Meaning of Chomsky Hierarchy

Chomsky Hierarchy defies the position of four different types of Languages in Theory of Computation. To visual Chomsky Hierarchy, go through this set diagram:

In short:

- Recursively enumerable Language is the largest set.
- Context Sensitive Language is a subset of Recursively enumerable Language
- Context Free Language is a subset of Context Free Language
- Regular Language is a subset of Context Free Language

### Type 0

Type 0 Language is the strongest class of Language is Theory of Computation. Formally, it is known as Recursively Enumerable Languages.

It involves all languages that can be generated using a Turing Machine. Turing Machine is the foundation of Computer Science and is the theoretical model representing Modern Computers and Quantum Computers as well.

### Type 1

Type 1 Language is a subset of Type 0 language. So, a Type 1 Language is always a Type 0 Language but a Type 0 Language is not always a Type 1 Language.

Type 1 Language is known as Context Sensitive Languages and are weaker than Type 0 Languages. These are the set of Languages that can be generated using Linear Bounded Automaton.

### Type 2

Type 2 Language is a subset of Type 1 language. So, a Type 2 Language is always a Type 1 Language but a Type 1 Language is not always a Type 2 Language.

Type 2 Language is known as Context Free Languages and are weaker than Type 1 and Type 0 Languages. These are the set of Languages that can be generated using Pushdown Automaton.

### Type 3

Type 3 Language is a subset of Type 2 language. So, a Type 3 Language is always a Type 2 Language but a Type 2 Language is not always a Type 3 Language.

Type 3 Language is known as Regular Languages and are weaker than Type 2, Type 1 and Type 0 Languages. These are the set of Languages that can be generated using Finite State Automaton.

# Modified / Complete Chomsky Hierarchy

The original Chomsky Hierarchy does not include Recursive Languages which are accepted by a Total Turing Machine which is a Turing Machine which always halts for any given input.

Recursive Language should idealy appear between Type 0 and Type 1.

Type | Language | Automata Machine |
---|---|---|

Type 0 | Recursively Enumerable | Turing Machine |

Type 0.5 | Recursive Language | Total/Halting Turing Machine |

Type 1 | Context Sensitive | Linear Bounded Automaton |

Type 2 | Context Free | Pushdown Automaton |

Type 3 | Regular | Finite State Automaton |

With this article at OpenGenus, you must have the complete idea of Chomsky Hierarchy which is an important milestone in Theory of Computation.