Extended Chomsky Hierarchy
Extended Chomsky Hierarchy is an modification of Chomsky Hierarchy by including Recursive Languages which comes in between Type 0 and Type 1 of Chomsky Hierarchy. It is extended beyond this to include all Computation Languages in Theory of Computation as well.
Prerequisite: 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. This results in "Extended Chomsky Hierarchy".
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 |
Note: Type 0.5 is the addition in Extended Chomsky Hierarchy. Other types are present in Chomsky Hierarchy as well. The original Chomsky Hierarchy is as follows:
| Type | Language | Automata Machine |
|---|---|---|
| Type 0 | Recursively Enumerable | Turing Machine |
| Type 1 | Context Sensitive | Linear Bounded Automaton |
| Type 2 | Context Free | Pushdown Automaton |
| Type 3 | Regular | Finite State Automaton |
There are several Computation Languages (> 200) that have been formally defined in the research of Theory of Computation. It is not possible to include every language in Chomsky Hierarchy as the idea is to keep it short and handy. Extended Chomsky Hierarchy covers the 5 most common Computation Languages which everyone should know.
If you would like to extend the "Extended Chomsky Hierarchy" further and want to classify all possible Computation Languages using it, we end up with this hierarchy:
It includes:
- Not finitely describable Language
- Not Recognizable Language
- Turing degrees Language
- Recognizable Language
- EXPSPACE complete Language
- EXPTIME complete Language
- PSPACE complete Language
- NP complete Language
- Context Free Language
- Deterministic Context Free Language
- Regular Languages Finite Language Language
- Presburger Arithmetic Language
- Decidable Language
and much more.
With this article at OpenGenus, you must have the complete idea of Chomsky Hierarchy which is an important milestone in Theory of Computation.