Chomsky Hierarchy

languages

Definition

Chomsky Hierarchy

The Chomsky hierarchy classifies formal languages by increasing expressive power. Its levels are regular languages (${\mathcal{L}}_3)$, context-free languages (${\mathcal{L}}_2)$, context-sensitive languages (${\mathcal{L}}_1$), recursive language (${\mathcal{L}}_{\text{rec}}$), and recursively enumerable languages (${\mathcal{L}}_0$).

Each class properly contains the one below it. Formally:

$${\mathcal{L}}_3⊊{\mathcal{L}}_2⊊{\mathcal{L}}_1⊊{\mathcal{L}}_{\text{rec}}⊊{\mathcal{L}}_0$$

Closure

Operation	${\mathcal{L}}_3$	${\mathcal{L}}_2$	${\mathcal{L}}_1$	${\mathcal{L}}_0$
Union	yes	yes	yes	yes
Concatenation	yes	yes	yes	yes
Kleene Star	yes	yes	yes	yes
Complement	yes	no	yes	no
Intersection	yes	no	yes	yes
Intersection with Regular Languages	yes	yes	yes	yes
Homomorphisms	yes	yes	no	yes
$\epsilon$-free homomorphism	yes	yes	yes	yes
gsm-mappings	yes	yes	no	yes
$\epsilon$-free gsm-mappings	yes	yes	yes	yes

Sub-languages

Being a subset does not determine the Chomsky type.

If $L^{\prime }\subseteq L$, then $L^{\prime }$ can be of the same type as $L$, a lower type, a higher type, or even lie outside the Chomsky hierarchy entirely.

Subset can have higher type

The regular language $a^{\ast }{b}^{\ast }{c}^{\ast }$ contains the context-sensitive language $\{a^n{b}^n{c}^n\mid n\ge 0\}$.

So a subset of a regular language can have higher Chomsky type than the language itself.

Subset can have lower type

The context-sensitive language $\{a^n{b}^n{c}^n\mid n\ge 0\}$ contains the context-free language $\{a^n{b}^n\mid n\ge 0\}$.

So a subset of a context-sensitive language can have lower Chomsky type than the language itself.

Subset can be arbitrary

The language ${\Sigma }^{\ast }$ is regular, but it contains every language over $\Sigma$, including languages that are not even recursively enumerable.

So a subset of a regular language can be arbitrarily complex.

Types

Type 0 - Unconstrained

Definition

Grammar

A grammar is defined as 4-tuple $G=⟨N,T,P,S⟩$, where

• $N$ is the finite set of non-terminal symbols,
• $T$ is the finite set of terminal symbols,
• $P\subseteq (N\cup T{)}^{+}\times (N\cup T{)}^{\ast }$ is the finite set of production rules (relation), and
• $S\in N$ is the start symbol.

Without further constraints, $G$ is called unconstrained grammar or type-0 grammar and is the most general form of a grammar in the Chomsky hierarchy.

Link to original

Type 1 - Context-Sensitive

Definition

Context-Sensitive Grammar (Type-1)

A grammar $G=(N,T,P,S)$ is called context-sensitive (Type-1) if every production rule in $P$ is context-sensitive.

In words: a single non-terminal symbol may be replaced by a nonempty string, but only in its surrounding context.

Link to original

Type 2 - Context-Free

Definition

Context-Free Grammar

A grammar $G=(N,T,P,S)$ is called context-free if every production rule in $P$ is context-free.

Equivalently: A language is called context-free there exists a pushdown automaton that accepts it.

Link to original

Type 3 - Regular

Definition

Regular Grammar

A grammar $G$ is called regular if every production rule is regular.

Link to original