What are the four levels of the Chomsky hierarchy?

From least to most powerful they are regular languages (Type 3), context-free languages (Type 2), context-sensitive languages (Type 1), and recursively enumerable languages (Type 0). Each level relaxes the restrictions on grammar rules and corresponds to a machine with more memory.

Is natural language captured by the Chomsky hierarchy?

The hierarchy was originally motivated by linguistics, but most linguists conclude that natural languages are not context-free, sitting at a level often called mildly context-sensitive. The hierarchy remains foundational in computer science even though human language fits it only loosely.

The Chomsky Hierarchy

The Chomsky hierarchy organizes formal languages into four nested classes, each defined by a restriction on grammar rules and matched to a distinct kind of abstract machine.

Definition

The Chomsky hierarchy is a classification of formal grammars by progressively stronger restrictions on their production rules, yielding the regular, context-free, context-sensitive, and recursively enumerable language classes in a chain of strict inclusions.

Scope

This topic covers the four grammar types — unrestricted, context-sensitive, context-free, and regular — their strict containment, and the automaton model corresponding to each level, namely the Turing machine, linear-bounded automaton, pushdown automaton, and finite automaton, along with the closure and decidability properties that separate the levels.

Core questions

How do restrictions on grammar rules translate into limits on memory and computing power?
Why is each level of the hierarchy strictly contained in the next?
Which automaton model corresponds to each grammar type?
How do decidability and closure properties change as one moves up the hierarchy?

Key theories

Grammar–machine correspondence: Each grammar class is recognized by a specific machine model — regular by finite automata, context-free by pushdown automata, context-sensitive by linear-bounded automata, and unrestricted by Turing machines — linking generative and operational descriptions of computation.
Strict inclusion of the language classes: Each level properly contains the one below it, witnessed by concrete separating languages, so the hierarchy is a genuine ladder of increasing expressive power rather than a collection of equivalent descriptions.

Clinical relevance

The hierarchy is the organizing map of formal language theory: it tells designers of programming languages, query languages, and protocol specifications how much machinery a given class of patterns requires, and it frames the boundary between what is decidable and what is only recognizable.

History

Chomsky proposed the hierarchy in the late 1950s while seeking formal models of natural-language syntax, and the machine correspondences were established as automata theory matured through the 1960s, with linear-bounded automata introduced by Myhill and the context-sensitive level clarified by Kuroda.

Key figures

Noam Chomsky
Marcel-Paul Schützenberger
John Myhill

Seminal works

hopcroft2006
sipser2013

Frequently asked questions

What are the four levels of the Chomsky hierarchy?: From least to most powerful they are regular languages (Type 3), context-free languages (Type 2), context-sensitive languages (Type 1), and recursively enumerable languages (Type 0). Each level relaxes the restrictions on grammar rules and corresponds to a machine with more memory.
Is natural language captured by the Chomsky hierarchy?: The hierarchy was originally motivated by linguistics, but most linguists conclude that natural languages are not context-free, sitting at a level often called mildly context-sensitive. The hierarchy remains foundational in computer science even though human language fits it only loosely.