Extended Chomsky Hierarchy

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

Free Linux Book

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:

extended-chomsky-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.