Chomsky hierarchy

Why it exists

The classes of languages met so far, regular, deterministic context-free and context-free, fit into a larger chain that ends with everything a computer can recognise. Noam Chomsky classified grammars by the shape of their productions; each shape matches a kind of machine. GATE asks for the chain, the machine of each class, strict inclusion with an example language for each step, and the type of a given grammar.

Prerequisites

You need the closure properties of both regular and context-free languages (regular closure, CFL closure); the top of the chain is the Turing machine (Turing machines).

Precise definitions

A grammar $G = (V, \Sigma, R, S)$ with productions $\alpha \to \beta$, $\alpha \in (V \cup \Sigma)^* V (V \cup \Sigma)^*$ (at least one variable on the left) and $\beta \in (V \cup \Sigma)^*$. The type of $G$:

(The name "context-sensitive" comes from the equivalent form $\alpha A \beta \to \alpha \gamma \beta$ with $\gamma \ne \varepsilon$: the variable $A$ is replaced only in the context $\alpha \_ \beta$; the form with $\lvert\alpha\rvert \le \lvert\beta\rvert$ is also called monotone or non-contracting; they generate the same languages, a textbook result.)

A language has type $k$ if some Type $k$ grammar generates it. The inclusions are

$\text{Type 3} \;\subsetneq\; \text{Type 2} \;\subsetneq\; \text{Type 1} \;\subsetneq\; \text{Type 0}.$

Between them sit the deterministic CFLs (between regular and context-free) and the recursive (decidable) languages (between context-sensitive and recursively enumerable).

How it works

The grammar types by example

The table gives six grammars; the program decides the type from the shape of the productions:

Points that the table makes:

• The type depends on the shape, not the language. $S \to aSb \mid AB$, $AB \to \varepsilon$ generates $\{a^n b^n\}$, which is context-free, but the production $AB \to \varepsilon$ has two symbols on the left and shrinks: the grammar is Type 0.
• A grammar whose productions are all right-linear or all left-linear is Type 3. A grammar that mixes them is not: $S \to aA$, $A \to Sb \mid b$ generates $a^n b^n$ ($n \ge 1$); it is context-free (Type 2) but not regular.
• Every regular grammar is context-free; every context-free grammar without $\varepsilon$-productions is context-sensitive (a variable replaced by a nonempty string never shrinks).

The strict inclusions and their witnesses

A grammar for $\{a^n b^n c^n : n \ge 1\}$ that is context-sensitive (no production shrinks):

$S \to aSBC \mid aBC, \qquad CB \to BC, \qquad aB \to ab, \quad bB \to bb, \qquad bC \to bc, \quad cC \to cc.$

Idea: generate $a^n (BC)^n$ first, let $B$'s and $C$'s sort themselves with $CB \to BC$ until all $B$'s precede all $C$'s, then convert from the left: $aB \to ab$, $bB \to bb$, $bC \to bc$, $cC \to cc$. Because no production shrinks the sentential form, membership is decidable by searching all sentential forms up to the length of the string; the program did exactly this and found that the language is $a^n b^n c^n$ with $n \ge 1$ (all strings up to length $12$) and that it accepts exactly those strings among all strings over $\{a, b, c\}$ up to length $9$.

Machines and decidability

• Type 3: finite automaton (DFA = NFA). Membership: linear time.
• Type 2: pushdown automaton. Membership: cubic time (CYK).
• Type 1: linear bounded automaton (a Turing machine whose head never leaves the cells of the input); membership is decidable (by the search above) but needs exponential time with the brute-force method.
• Type 0: Turing machine; membership is only semi-decidable: the machine halts and accepts strings of the language but may run forever on others (decidable and recognisable languages).

Closure summary (quoted textbook results)

Complement is the revealing column: the context-sensitive languages are closed under complement (Immerman and Szelepcsényi, a nontrivial theorem), while the recursively enumerable languages are not; a language is recursive exactly when it and its complement are both recursively enumerable (decidable and recognisable languages).

Worked examples

Cheat box

Traps and GATE patterns

Connections

The top of the hierarchy is explained by Turing machines and by decidability (Turing machines, decidable and recognisable languages); the deterministic subclass sits between regular and context-free (DPDA versus NPDA); the regular and context-free closure tables are on the pages for those classes.

PYQs

Consider the regular grammar:
S → Xa | Ya
X → Za
Z → Sa | ε
Y → Wa
W → Sa
where S is the starting symbol, the set of terminals is
{a} and the set of non-terminals is {S, W, X, Y, Z}. We
wish to construct a deterministic finite automaton
(DFA) to recognize the same language. What is the
minimum number of states required for the DFA?

Consider the following languages:
L1 = { anwan | w ∈ {a, b}* }
L2 = { wxwr | w, x ∈ {a, b}*, |w|, |x| > 0 }
Note that wr is the reversal of the string w. Which of
the following is/are TRUE?

Consider the following languages:
L1 = {ap│p is a prime number}
L2 = {anbmc2m | n ≥ 0, m ≥ 0}
L3 = {anbnc2n │ n ≥ 0}
L4 = {anbn │ n ≥ 1}
Which of the following are CORRECT?
I. L1 is context-free but not regular.
II. L2 is not context-free.
III. L3 is not context-free but recursive.
IV. L4 is deterministic context-free.

Language L1 is defined by the grammar:
S1 → aS1b|ε
Language L2 is defined by the grammar:
S2 → abS2|ε
Consider the following statements:
P: L1 is regular
Q: L2 is regular
Which one of the following is TRUE?

Consider the languages L1,L2 and L3 as given below:
L1 = { 0p 1q | p, q ∈ N },
L2 = { 0p 1q | p, q ∈ N and p = q } and
L3 = { 0p 1q 0r | p, q, r ∈ N and p = q = r }.
Which of the following statements is NOT TRUE?

Match the following:

E. Checking that
identifiers are
declared before
their use
P. L={ anbmcndm |n≥1,m≥1}
F. Number of formal
parameters in the
declaration of a
function agrees with
the number of actual
parameters in a use of
that function
Q. X→XbX | XcX | dXf | g
G. Arithmetic
expressions with
matched pairs of
parentheses
R. L={wcw|w∈ (a+b)* }
H. Palindromes
S. X→bXb | cXc | ε

For s ∈ (0+1)* let d(s) denote the decimal value of s (e.g.
d(101)=5 ). Let L={s∈(0+1)* |d(s) mod 5=2 and d(s)
mod 7≠4}
Which one of the following statements is true?

Consider the languages:
L1 = {anbncm | n, m > 0} and L2 = {anbmcm | n, m > 0},
Which one of the following statements is FALSE?

The language {0n1n2n | 1<=n<=106} is

Let L= L1 ∩ L2 , where L1 and L2 are languages as
defined below:
L1={ambmcnbn | m,n >=0}
L2={aibjck | i,j,k >=0}
Then is L

Which of the following is true for the language
{ ap| p is prime} ?

Self-check

Revision card

References