Chomsky Hierarchy and Language Classes: short notes (Theory of Computation)

Revision mode

Introduction

The Chomsky hierarchy organizes grammars and their languages into four classical types: regular (Type-3), context-free (Type-2), context-sensitive (Type-1), and unrestricted (Type-0). Matching machine models are finite automata, PDAs, linear bounded automata (LBAs), and Turing machines. The hierarchy is used for inclusion questions, example witnesses, and closure/decidability contrasts. This note summarises the map; it is not a deep dive into LBAs.

Three kinds of question arise here: which class a language belongs to (tightest class), which grammar type a rule set is, and which machine model matches which class. The finer ladder with DCFL and the decidable languages matters as much as the four classical types.

Prerequisites

Turing Machines: Type-0 machine model.
Earlier TOC notes on regular and context-free languages.

Core concepts

The four types

Type	Grammar restriction	Machine	Languages
3	$A \to xB$ , $A \to x$ (all right-linear) or all left-linear, $x \in \Sigma^*$	FA	Regular
2	$A \to \alpha$ , $\alpha \in (V \cup \Sigma)^*$	PDA	Context-free
1	$\alpha A \beta \to \alpha \gamma \beta$ with $\gamma \ne \varepsilon$ ; equivalently non-contracting $\alpha \to \beta$ with $\lvert\alpha\rvert \le \lvert\beta\rvert$ ; $S \to \varepsilon$ allowed only if $S$ is on no right side	LBA	Context-sensitive
0	$\alpha \to \beta$ , $\alpha$ contains a variable	TM	Recursively enumerable

Mixing right-linear and left-linear rules in one grammar leaves Type 3: $S \to aT$ , $T \to Sb \mid b$ generates $\{a^n b^n \mid n \ge 1\}$ . Such linear grammars (at most one variable on each right side) give a class strictly between REG and CFL.

Inclusions

\mathrm{REG} \subsetneq \mathrm{CFL} \subsetneq \mathrm{CSL} \subsetneq \mathrm{RE},

and the finer ladder is

\text{finite} \subsetneq \mathrm{REG} \subsetneq \mathrm{DCFL} \subsetneq \mathrm{CFL} \subsetneq \mathrm{CSL} \subsetneq \mathrm{REC} \subsetneq \mathrm{RE} \subsetneq \text{all languages}.

Every CSL is decidable, because an LBA on input $w$ has only finitely many configurations ( $|Q| \cdot (|w|+2) \cdot |\Gamma|^{|w|+2}$ ), so a decider can search the configuration graph for an accepting configuration (or cut every run off after that many steps) and always halt. Watching a single run for a repeat is not enough, because an LBA is nondeterministic. The inclusion is strict by diagonalization over an enumeration of LBAs; no "natural" witness is needed for GATE.

Nested Chomsky hierarchy with machines and grammar types — Figure 1. Nested language classes REG subset CFL subset CSL subset RE, each annotated with its grammar type and machine model (FA, PDA, LBA, TM).

Witnesses

Regular but not finite: $a^*$ .
CFL not regular: $a^n b^n$ .
CSL not CFL: $a^n b^n c^n$ .
RE not recursive: $A_{\mathrm{TM}}$ (next note).
DCFL not regular: $a^n b^n$ . CFL not DCFL: $\{ww^R\mid w\in\{a,b\}^*\}$ , $\{a^i b^j c^k \mid i = j \text{ or } j = k\}$ .
Not RE: $\overline{A_{\mathrm{TM}}}$ .

How it works

Right-linear grammars = regular

Productions $A \to xB$ or $A \to x$ with $x \in \Sigma^*$ generate regular languages; convert to/from NFAs by treating variables as states.

Unrestricted grammars = TMs

Type-0 productions $\alpha \to \beta$ ( $\alpha$ nonempty) generate exactly the r.e. languages.

Algorithms and pseudocode

Membership:

Regular: DFA run linear time.
CFL: CYK cubic time.
CSL: decidable (LBA space), expensive.
RE: semidecidable (enumerate TM acceptors).

Mathematical explanation

Properness of inclusions

Each witness separates adjacent classes: $a^n b^n$ has infinitely many Myhill-Nerode classes (the prefixes $a^i$ are pairwise distinguishable by $b^i$ ), $a^n b^n c^n$ fails the CFL pumping lemma, and $A_{\mathrm{TM}}$ is undecidable by diagonalization.

A context-sensitive grammar for $a^n b^n c^n$

$S \to aSBC \mid aBC$ , $CB \to BC$ , $aB \to ab$ , $bB \to bb$ , $bC \to bc$ , $cC \to cc$ . Every rule is non-contracting. Derivation of aabbcc: $S \Rightarrow aSBC \Rightarrow aaBCBC \Rightarrow aaBBCC \Rightarrow aabBCC \Rightarrow aabbCC \Rightarrow aabbcC \Rightarrow aabbcc$ . The rule $CB \to BC$ sorts the variables; $aB \to ab$ and $bB \to bb$ turn $B$ 's into $b$ 's only once they sit right after the $a$ 's or $b$ 's, so letters never get out of order. Because no rule shrinks a sentential form, membership of $w$ can be decided by searching only forms of length $\le |w|$ , which is the grammar view of "CSL $\subseteq$ REC".

Decidable versus r.e.

Recursive languages are those decided by total TMs; they properly contain the context-sensitive languages under standard textbook presentations used in GATE, and are properly contained in RE.

Worked examples

Example 1: place the language

Language	Class (tight)
$\{a,b\}^*$	regular
$\{a^n b^n\}$	CFL, not regular
$\{a^n b^n c^n\}$	CSL, not CFL
$A_{\mathrm{TM}}$	RE, not recursive

Example 2: grammar type check

$S \to aS \mid \varepsilon$ right-linear (Type-3). $S \to aSb \mid \varepsilon$ Type-2. The rule $aAb \to aabb$ rewrites $A$ as $ab$ in the context $a\_b$ , so it is Type-1. $AB \to A$ is contracting, so it is Type-0 only. $S \to SS \mid a$ is Type-2 although its language $a^+$ is regular: the type of a grammar is set by the rule shapes, the class of a language by the best grammar that exists for it.

Example 3: machine upgrade

FA cannot store $n$ for $a^n b^n$ ; PDA can; PDA cannot store two independent counts for $a^n b^n c^n$ ; TM can.

Example 4: closure glance

Regular languages, DCFLs, CSLs and decidable languages are closed under complement; CFLs and RE languages are not. CSL closure under complement is the Immerman-Szelepcsenyi theorem. The full table across all classes is in Closure and Decision Properties of CFLs.

Example 5: exam diagram

Draw nested ovals labelled REG, CFL, CSL, RE and write each witness inside the ring of the smallest class that contains it: $a^n b^n$ in the CFL ring outside REG, $a^n b^n c^n$ in the CSL ring outside CFL, $A_{\mathrm{TM}}$ in the RE ring.

Example 6: tightest class

Language	Tightest class	Why
$\{a^n b^n \mid n \le 1000\}$	regular	finite
$\{a^m b^n \mid m \ne n\}$	DCFL	one counter, decided at end of input
$\{w \in \{a,b\}^* \mid \#_a(w) = \#_b(w)\}$	DCFL	counter with a sign
$\{ww^R\mid w\in\{a,b\}^*\}$	CFL, not DCFL	the centre must be guessed
$\{ww\mid w\in\{a,b\}^*\}$ , $\{a^n b^n c^n\}$ , $\{a^{n^2}\}$ , $\{a^{2^n}\}$ , $\{a^q \mid q \text{ prime}\}$	CSL, not CFL	each is decided in linear space
$\{\langle G \rangle \mid G \text{ a CFG with } L(G) = \emptyset\}$	decidable; known CSL upper bound under the ordinary grammar encoding, not a tightest-class claim	marking generating variables
$HALT_{\mathrm{TM}}$ , $A_{\mathrm{TM}}$	RE, not co-RE	simulate; diagonalization
$\overline{A_{\mathrm{TM}}}$ , $E_{\mathrm{TM}}$	co-RE, not RE	complement of an RE, undecidable language
$EQ_{\mathrm{TM}}$	neither RE nor co-RE	$\overline{A_{\mathrm{TM}}} \le_m EQ_{\mathrm{TM}}$ and $A_{\mathrm{TM}} \le_m EQ_{\mathrm{TM}}$

Traps: a subset of a regular language need not be regular ( $a^n b^n \subseteq a^*b^*$ ); a finite union of regular languages is regular, an infinite union need not be ( $\bigcup_n \{a^n b^n\}$ ); every finite language is regular, however complicated its definition.

Important properties and observations

Hierarchy is about descriptive power, not asymptotic runtime.
Ambiguity, determinism (DCFL) and decidability cut across the hierarchy with their own subclasses.
An LBA is a nondeterministic TM whose head never leaves the input; whether deterministic LBAs are as powerful is an open problem.
Type-0 grammars and TMs are equivalent: a TM can enumerate all derivations, and a grammar can simulate a TM run backwards.

Common misconceptions.

"CSL means 'almost CFL'." CSLs properly contain CFLs; $a^n b^n c^n$ is the emblem.
"RE means regular expression." In computability, RE means recursively enumerable.
"All TM languages are decidable." Only the recursive ones.
"Every CSL is a CFL with context." CSLs contain all CFLs, and also non-CFLs such as $a^n b^n c^n$ .
"A grammar with a left-linear and a right-linear rule is still regular." Mixed linear grammars can generate $a^n b^n$ .

GATE examination perspective

NESTED DRAWING. Four classes with witnesses.
VOCABULARY. RE vs regular expression vs recursive.
MACHINE MATCHING. FA/PDA/LBA/TM.
LIGHT CSL. Do not invent LBA transition tables unless asked.
TIGHTEST CLASS. An option may name a true but loose class; pick the smallest one.
GRAMMAR VERSUS LANGUAGE. A Type-2 grammar can generate a regular language.
FINITE IS REGULAR. Any bound on $n$ makes the language finite.

Summary

Sources

P. Linz, An Introduction to Formal Languages and Automata, 6th ed., Jones & Bartlett Learning, Section 11.1 (recursive and recursively enumerable languages), Section 11.2 (unrestricted grammars), Section 11.3 (context-sensitive grammars and languages; relation between recursive and context-sensitive languages), Section 11.4 (the Chomsky hierarchy), Section 10.5 (linear bounded automata).
J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson Addison-Wesley: Section 9.1 (a language that is not recursively enumerable), Section 9.2 (an undecidable problem that is RE).
M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning: Section 4.2 (undecidability; a Turing-unrecognizable language).