Chapter 29 of 34

Chomsky Hierarchy & Linear Bounded Automata

We have now met four kinds of machines: finite automata, pushdown automata, linear bounded automata (in this chapter) and Turing machines. We have also met different kinds of grammars: regular grammars and context-free grammars. In 1956 the linguist Noam Chomsky noticed that grammars can be arranged in a ladder simply by restricting the shape of their production rules, and that each rung of the ladder matches one kind of machine.

This ladder, the Chomsky hierarchy, is the map of the whole subject. It tells you, for any language, which grammar can generate it, which machine can recognise it, which operations it survives, and which questions about it can be answered by an algorithm.

The Chomsky hierarchy classifies grammars into four types: Type 0 (unrestricted), Type 1 (context-sensitive), Type 2 (context-free) and Type 3 (regular). They generate, respectively, the recursively enumerable, context-sensitive, context-free and regular languages, which are accepted by Turing machines, linear bounded automata, pushdown automata and finite automata. Each class is a proper subset of the one above it.

The context-sensitive grammar in this chapter was checked by a program that generates every terminal string up to length 21, and the program also caught a classic mistake in a "textbook-style" conversion, which we show you so you can avoid it.


Grammars in General

A grammar is G = (V, T, P, S): variables, terminals, productions and a start symbol. In the most general form a production is

α → β        where α, β ∈ (V ∪ T)*  and  α contains at least one variable

A derivation step replaces any occurrence of a left side α in the current sentential form by β. The four types differ only in which α → β are allowed.


The Four Types

Type 3: Regular grammars

A → aB    or    A → a    (or A → ε)          right-linear
(or all rules left-linear:  A → Ba | a)

At most one variable, always at the same end. Equivalent to finite automata (see Regular Grammars). Mixing left-linear and right-linear rules in one grammar can produce non-regular languages, so a "regular grammar" must be consistently one or the other.

Type 2: Context-free grammars

A → γ        A is a single variable,  γ ∈ (V ∪ T)*

The left side is a lone variable, so A can be replaced regardless of what surrounds it: the context does not matter. Equivalent to pushdown automata.

Type 1: Context-sensitive grammars (CSG)

α A β → α γ β       A a variable,  α, β ∈ (V ∪ T)*,  γ ≠ ε

A may be replaced by γ, but only when it appears with left context α and right context β. Because γ ≠ ε, sentential forms never shrink. One exception is allowed: S → ε, provided S never appears on any right side (so that ε can be in the language).

An equivalent and easier-to-check form is the noncontracting (monotonic) grammar: every rule α → β has |α| ≤ |β| (again with the S → ε exception). Every CSG is noncontracting, and every noncontracting grammar can be converted to a CSG generating the same language, so both define the same class. Many exam questions classify grammars using the noncontracting test.

Type 0: Unrestricted grammars

α → β        any α containing a variable, any β (even ε)

Rules may shrink the string. Unrestricted grammars generate exactly the languages accepted by Turing machines: the recursively enumerable languages.

The hierarchy

Type

Grammar

Rule form

Language class

Machine

0

Unrestricted

α → β

Recursively enumerable

Turing machine

1

Context-sensitive

αAβ → αγβ, γ ≠ ε (or |α| ≤ |β|)

Context-sensitive

Linear bounded automaton

2

Context-free

A → γ

Context-free

Pushdown automaton (nondeterministic)

3

Regular

A → aB | a | ε

Regular

Finite automaton

┌───────────────────────────────────────────────────────────┐
│ All languages           (e.g. L_d, the diagonal language) │
│  ┌──────────────────────────────────────────────────────┐ │
│  │ Type 0: Recursively enumerable    (e.g. L_u)         │ │
│  │  ┌────────────────────────────────────────────────┐  │ │
│  │  │ Recursive (decidable)  -- not a Chomsky type   │  │ │
│  │  │  ┌──────────────────────────────────────────┐  │  │ │
│  │  │  │ Type 1: Context-sensitive  (a^n b^n c^n) │  │  │ │
│  │  │  │  ┌────────────────────────────────────┐  │  │  │ │
│  │  │  │  │ Type 2: Context-free   (a^n b^n)   │  │  │  │ │
│  │  │  │  │  ┌──────────────────────────────┐  │  │  │  │ │
│  │  │  │  │  │ Type 3: Regular  ((a+b)*abb) │  │  │  │  │ │
│  │  │  │  │  └──────────────────────────────┘  │  │  │  │ │
│  │  │  │  └────────────────────────────────────┘  │  │  │ │
│  │  │  └──────────────────────────────────────────┘  │  │ │
│  │  └────────────────────────────────────────────────┘  │ │
│  └──────────────────────────────────────────────────────┘ │
└───────────────────────────────────────────────────────────┘

Every inclusion is proper, and each has a witness:

Inclusion

A language in the bigger class but not the smaller

Regular ⊂ CFL

{anbn : n ≥ 0}

CFL ⊂ CSL

{anbncn : n ≥ 1}, {ww}, {ap : p prime}

CSL ⊂ Recursive

exists, by a diagonal argument over all CSGs (no simple natural example)

Recursive ⊂ RE

Lu = {⟨M, w⟩ : M accepts w}, and the halting problem

RE ⊂ all languages

Ld, the diagonalization language

Two refinements are often asked: DCFLs (deterministic PDAs) sit strictly between regular languages and CFLs, and the recursive languages (TMs that always halt) sit between CSLs and RE languages. Neither is one of Chomsky's four types. The last two rows are explained in Decidability: Recursive & Recursively Enumerable Languages and Halting Problem & Undecidability.


Identifying the Type of a Grammar

Always classify by the most restrictive type whose rules every production satisfies. Check from Type 3 upwards.

Productions

Highest type

Why

S → aS | bA, A → b

Type 3

all right-linear

S → aSb | ab

Type 2

single variable on the left; the variable is in the middle, so not regular

S → aSBc | abc, cB → Bc, bB → bb

Type 1

cB → Bc has two symbols on the left (not CF), but no rule shrinks

S → aSb | ε, AB → B

Type 0

AB → B shrinks (|AB| = 2 > 1); also S → ε with S on a right side is not allowed in Type 1

AB → BA (plus S → AB...)

Type 1

noncontracting (2 ≤ 2); it is not literally of the form αAβ → αγβ, but it can be simulated by such rules

Note that a grammar's type and its language's type can differ: the grammar S → AB, A → a, B → b is Type 2, but its language {ab} is regular (it also has a Type 3 grammar). A language's type is the most restrictive type of any grammar that generates it.


A Context-Sensitive Grammar for {anbncn : n ≥ 1}

The idea is the same as moving cards into sorted order: first generate the right number of a's, B's and C's, then sort the B's and C's, then convert them to terminals only when they are in the right place.

1. S  → a S B C          generate one a, one B, one C per round
2. S  → a B C            last round
3. C B → B C             sort: move B's left past C's
4. a B → a b             the first B after the a's becomes b
5. b B → b b             each next B becomes b
6. b C → b c             the first C after the b's becomes c
7. c C → c c             each next C becomes c

Rules 1 and 2 give an(BC)n. Rule 3 lets us reorder to anBnCn. Rules 4 to 7 convert left to right, and they only fire for a symbol that is in its correct position: a B can become b only right after an a or b, a C only right after a b or c. Every rule is noncontracting.

Derivation of aabbcc:

S  ⇒ aSBC        (1)
   ⇒ aaBCBC      (2)
   ⇒ aaBBCC      (3)  CB → BC
   ⇒ aabBCC      (4)  aB → ab
   ⇒ aabbCC      (5)  bB → bb
   ⇒ aabbcC      (6)  bC → bc
   ⇒ aabbcc      (7)  cC → cc

Why nothing wrong is generated: the numbers of a's, (B or b) and (C or c) are always equal, since rules 1 and 2 add one of each and rules 3 to 7 only reorder or convert. If a C is converted to c too early (say, with a B still to its right), the B after it can never become b (no rule cB → cb) and can never move left past the c (rule 3 needs a capital C). So that derivation gets stuck with a variable and produces no terminal string. Our program generated all terminal strings of length ≤ 21 and got exactly abc, aabbcc, ..., a7b7c7.

Making it strictly context-sensitive (a trap!)

Rule 3, CB → BC, changes two symbols at once, so it is noncontracting but not of the form αAβ → αγβ. To convert it we change one symbol at a time, each in a context. A tempting conversion uses a single helper X:

CB → XB,   XB → XC,   XC → BC          WRONG

The program found that this generates aaabbcccc, which has the wrong counts! The problem: two half-finished swaps can interfere. Start from CBB (one C, two B's):

CBB ⇒ XBB    (CB → XB)
    ⇒ XCB    (XB → XC)      first swap half done
    ⇒ XXB    (CB → XB)      a second swap starts on the new C
    ⇒ XXC    (XB → XC)
    ⇒ XBC    (XC → BC)      second swap finishes
    ⇒ XCC    (XB → XC)      the first X grabs the wrong B
    ⇒ BCC    (XC → BC)      now one B and two C's!

The first X was supposed to finish with XC → BC, but the B it left behind got used by another swap. A correct conversion uses two fresh helpers so each swap is completed as a unit:

CB → XB,   XB → XY,   XY → BY,   BY → BC          (X, Y new variables)

Each rule rewrites exactly one symbol in a context (C → X before B; B → Y after X; X → B before Y; Y → C after B). The program confirmed that this version generates exactly {anbncn} up to length 15. Lesson: grammar constructions that "obviously work" should be tested.


Linear Bounded Automata (LBA)

If a Turing machine is given an unlimited tape, it can accept every RE language. What if it is allowed to use only the cells occupied by its input?

A linear bounded automaton is a nondeterministic Turing machine whose input is enclosed between a left end marker ¢ and a right end marker $. The head may never move left of ¢ or right of $, and may never overwrite them. So the machine can use only the |w| cells holding the input (plus the two markers) as its working space.

      | ¢ | a | a | b | b | c | c | $ |        the whole usable tape
            ▲
        read/write head, trapped between ¢ and $

Why "linear"? An LBA can use a larger tape alphabet, so each cell can hold, say, a k-tuple of symbols on k tracks. That gives it k · |w| "virtual cells". Any constant multiple of the input length can be simulated, so the space bound is linear in |w|, not just |w|.

Theorem (Kuroda, 1964): a language is context-sensitive if and only if it is accepted by some LBA (when ε is excluded or handled separately).

Intuition. CSG → LBA: since rules never shrink, every sentential form in a derivation of w has length at most |w|, so the LBA can guess a derivation backwards inside the input cells: repeatedly pick a place where some β occurs and replace it by α, until only S remains. LBA → CSG: a noncontracting grammar can simulate the LBA's moves on a sentential form that has the same length as the tape, keeping a copy of the original input on a second "track" inside each symbol, so the final string can be produced without shrinking.

An LBA for {anbncn}

The X/Y/Z marking TM from Turing Machines never writes outside the input; it only steps onto the first blank after the input in its final check (state q4). Replace that blank by the end marker $, and let the move δ(q4, $) go to the accepting state while moving left (an LBA may not move past $), and it never leaves the input region: it is an LBA (a deterministic one, in fact). Most "mark and zig-zag" machines are LBAs.

Membership is decidable for CSLs

An LBA with s states and tape alphabet of size g, on input of length n, has at most

s × (n + 2) × g^n      different configurations   (state × head position × tape contents)

For example, with s = 5, g = 4 and n = 10: 5 × 12 × 410 = 62,914,560. A computation that runs longer than that must repeat a configuration, so it is in a loop and can be cut off. For a nondeterministic LBA, an algorithm can search the finite graph of configurations for a path to an accepting one. Either way it always halts, so every CSL is recursive. (Equivalently: with a noncontracting grammar, all sentential forms of length ≤ |w| can be listed and searched.)

Two famous "LBA problems"

  • Is every CSL accepted by a deterministic LBA? (Is DLBA = LBA?) This is still open, posed by Kuroda in 1964. It is the space analogue of P vs NP.

  • Are CSLs closed under complement? Yes, proved independently by Immerman and by Szelepcsényi (1987–88) using an ingenious counting technique, which shows nondeterministic linear space is closed under complement.


Closure Properties Across the Hierarchy

Operation

Regular

CFL

CSL

Recursive

RE

Union

Yes

Yes

Yes

Yes

Yes

Intersection

Yes

No

Yes

Yes

Yes

Complement

Yes

No

Yes

Yes

No

Concatenation

Yes

Yes

Yes

Yes

Yes

Kleene star

Yes

Yes

Yes

Yes

Yes

Reversal

Yes

Yes

Yes

Yes

Yes

Intersection with regular

Yes

Yes

Yes

Yes

Yes

Homomorphism (arbitrary)

Yes

Yes

No (only ε-free)

No (only ε-free)

Yes

Inverse homomorphism

Yes

Yes

Yes

Yes

Yes

Two entries deserve a comment. CSLs and recursive languages are not closed under homomorphisms that erase symbols (h(a) = ε): erasing can hide an unbounded amount of "scratch work", and in fact every RE language is an erasing homomorphic image of some CSL. RE languages are closed under union and intersection but not complement; complement is treated in Decidability: Recursive & Recursively Enumerable Languages.


Decision Problems Across the Hierarchy

Question

Regular

DCFL

CFL

CSL

Recursive

RE

Membership (w ∈ L?)

D

D

D

D

D

U

Emptiness (L = ∅?)

D

D

D

U

U

U

Finiteness

D

D

D

U

U

U

Universality (L = Σ*?)

D

D

U

U

U

U

Equivalence (L1 = L2?)

D

D

U

U

U

U

Containment (L1 ⊆ L2?)

D

U

U

U

U

U

(D = decidable, U = undecidable. For the recursive column the language is given by a TM known to halt on every input.) The pattern: the bigger the class, the fewer questions you can answer. Membership survives all the way up to recursive languages, which is exactly their definition; emptiness is lost as soon as we pass context-free languages.


Classifying Languages: Solved Examples

Language

Smallest class

Reason

(a + b)*abb

Regular

a DFA with 4 states

{ambn : m, n ≥ 0}

Regular

it is just a*b*, no counting needed

{anbn}

DCFL

needs counting (pumping lemma), a DPDA suffices

{wwR : w ∈ {a, b}*}

CFL (not DCFL)

the PDA must guess the middle

{aibjck : i = j or j = k}

CFL (inherently ambiguous)

union of two CFLs

{anbncn}

CSL

CSG above; not CFL by the pumping lemma

{ww : w ∈ {a, b}*}

CSL

an LBA compares the halves in place

{an²}, {a2n}, {ap : p prime}

CSL

checkable in linear space; not CFL (a unary CFL is regular, and these are not)

{⟨M, w⟩ : M accepts w}

RE, not recursive

universal TM accepts it; undecidable

{⟨M⟩ : M does not accept ⟨M⟩}

not RE

diagonalization


Common Mistakes

  • Thinking "recursive" is a Chomsky type. The four types are 0, 1, 2, 3. Recursive languages lie strictly between Type 1 and Type 0.

  • Classifying a language by the given grammar. A Type 2 grammar may generate a regular language. Ask whether a simpler grammar exists.

  • Allowing ε-rules freely in Type 1. Only S → ε, and only if S never appears on a right-hand side.

  • Saying LBAs are deterministic by definition. The standard LBA is nondeterministic; whether deterministic LBAs are equally powerful is an open problem.

  • Saying CSLs are not closed under complement. They are (Immerman–Szelepcsényi). It is CFLs and RE languages that are not.

  • Saying emptiness is decidable for CSLs because membership is. Membership in CSLs is decidable, emptiness is not.


Practice and GATE-Style Questions

Q1. Classify the grammar S → aAb, aA → aaAb, A → ε.

aA → aaAb has two symbols on the left, so it is not context-free. A → ε shrinks the string and A is not the start symbol, so it is not context-sensitive either. The grammar is Type 0. (Its language is {anbn : n ≥ 1}, which is context-free: a grammar's type is not its language's type.)

Q2. Which is the correct chain of proper inclusions: (a) Regular ⊂ CFL ⊂ RE ⊂ CSL (b) Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ Recursive ⊂ RE (c) Regular ⊂ CFL ⊂ DCFL ⊂ CSL?

(b).

Q3. An LBA has 6 states and a tape alphabet of 5 symbols (end markers not counted). How many configurations can it have on an input of length 4?

6 × (4 + 2) × 54 = 6 × 6 × 625 = 22,500. (Head positions include the two end markers; some textbooks count only the n input cells, giving 6 × 4 × 625 = 15,000. State your convention.)

Q4. Which of these problems is decidable: (a) Is w ∈ L(G) for a CSG G? (b) Is L(G) = ∅ for a CSG G? (c) Is L(M) = ∅ for an LBA M?

Only (a). (b) and (c) are the same problem (emptiness of CSLs) and it is undecidable.

Q5. True or false: every context-sensitive language is recursive, and every recursive language is context-sensitive.

The first is true (LBA configurations are finite, so membership can be decided). The second is false: there are recursive languages that are not context-sensitive, shown by diagonalizing over an enumeration of all CSGs.

Q6. In the CSG for anbncn above, the derivation S ⇒ aSBC ⇒ aaBCBC ⇒ aabCBC ⇒ aabcBC is legal. Can aabcBC lead to a terminal string?

No. The C right after b was converted to c too early. Now B sits right after the terminal c: there is no rule with left side cB, and B can only move by CB → BC, which needs a capital C on its left. The final C cannot be converted either, because bC → bc and cC → cc need b or c immediately before it, and B is there. The derivation is stuck. This is how the grammar stays correct: a wrong order of conversions never produces a wrong terminal string, it simply produces nothing.


Summary

  • Chomsky hierarchy: Type 3 regular (FA) ⊂ Type 2 context-free (PDA) ⊂ Type 1 context-sensitive (LBA) ⊂ Type 0 recursively enumerable (TM), all inclusions proper.

  • Rule shapes: A → aB | a; A → γ; αAβ → αγβ with γ ≠ ε (equivalently noncontracting |α| ≤ |β|); α → β.

  • Between the types: DCFL between regular and CFL; recursive between CSL and RE.

  • An LBA is a nondeterministic TM confined to its input between end markers; LBAs accept exactly the CSLs.

  • CSL membership is decidable (finitely many configurations), so CSL ⊂ recursive; CSL emptiness is undecidable.

  • CSLs are closed under union, intersection, complement (Immerman–Szelepcsényi), concatenation and star. DLBA = LBA is open.

  • {anbncn} has the CSG S → aSBC | aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC → cc.

Restrict the rules, and you lose generating power but gain answerable questions. The Chomsky hierarchy is the trade-off table between what a formalism can describe and what we can decide about it.