# Chomsky Hierarchy

Get FREE domain for 1st year and build your brand new site

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.

1. Chomsky Hierarchy
2. Meaning of Chomsky Hierarchy
3. 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.