Overview

Chomsky hierarchy


Show Summary Details

Quick Reference

A series of four classes of formal languages whose definition in 1959 by Noam Chomsky marked the beginning of formal language theory, and that have ever since remained central to the subject. In increasing complexity they are called type 3, type 2, type 1, and type 0, each one a subclass of the next. Each type can be defined either by a class of grammars or by a class of automata, as indicated in the table. Type 0 consists of all recursively enumerable languages. Type 1 is a subclass of the languages recognizable by primitive recursive functions. Languages in types 2 and 3 can be recognized by a Turing machine in cubic and linear time, respectively.

Chomsky hierarchy.

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.