EXERCISES
* 1. Find context-sensitive grammars for the following languages.
(a) L = {a + b n c n-1 : n ≥ 1}
(b) L = {a n b n a 2n : n ≥ 1}.
(c) L = {a n b m c n d m : n ≥ 1, m ≥ 1}.
(d) L = {ww : w ∈ {a, b + }.
(e) L = {a n b n c n d n : n ≥ 1},
* 2. Find context-sensitive grammars for the following languages.
(a) L = { w : n a (w) = n b (w) = n c (w)
(b) L = { w : n a (w) = n b (w) < n c (w)
3. Show that the family of context-sensitive languages is closed under union.
4. Show that the family of context-sensitive languages is closed under reversal.
5. For m in Theorem 11.10, give explicit bounds for m as a function of |w| and |V
∪ T|
6. Without explicitly constructing it, show that there exists a context-sensitive
grammar for the language L = {wuw R : w, u ∈ {a, b} + , |w| ≥ |u|}.
11.4 The Chomsky Hierarchy
We have now encountered a number of language families, among them the
recursively enumerable languages (L RE ), the context-sensitive languages (L CS ),
the context-free languages (L CF ), and the regular languages(L REG ). One way of
exhibiting the relationship between these families is by the Chomsky hierarchy.
Noam Chomsky, a founder of formal language theory, provided an initial
classification into four language types, type 0 to type 3. This original
terminology has persisted and one finds frequent references to it, but the numeric
types are actually different names for the language families we have studied.
Type 0 languages are those generated by unrestricted grammars, that is, the
recursively enumerable languages. Type 1 consists of the context-sensitive
languages, type 2 consists of the context-free languages, and type 3 consists of