In this section, we prove that the class of context-sensitive languages is closed under union, concatenation and Kleene-star. It is also closed under the other set theoretical operations.

**Theorem 28.** *The class of context-sensitive languages is closed under the regular operations.*

**Proof.** The proof is constructive. Let *L*_{1} and
*L*_{2} be two context-sensitive languages.
Let the monotone grammars *G*_{1} = (*N*_{1},
*T, S*_{1}, *P*_{1}) and
*G*_{2} = (*N*_{2},
*T, S*_{2}, *P*_{2}) be in Kuroda normal form and generate the languages
*L*_{1} and *L*_{2}, respectively,
such that *N*_{1} ∩ *N*_{2} = ∅
(this can be done by renaming nonterminals of a grammar without affecting the generated language).

First, we show the closure under union.

If λ ∉

*L*_{1}∪*L*_{2}, then let*G*= (*N*_{1}∪*N*_{2}∪ {*S*},*T, S, P*_{1}∪*P*_{2}∪ {*S*→*S*_{1},*S*→*S*_{2}}),where

*S*∉*N*_{1}∪*N*_{2}, a new symbol. It can be seen that*G*generates the language*L*_{1}∪*L*_{2}.If λ ∈

*L*_{1}∪*L*_{2}(i.e.,*S*_{1}→ λ ∈*P*_{1}and/or*S*_{2}→ λ ∈*P*_{2}), then let*G*= (*N*_{1}∪*N*_{2}∪ {*S*},*T, S*,*P*_{1}∪*P*_{2}∪ {*S*→*S*_{1},*S*→*S*_{2},*S*→ λ} \ {*S*_{1}→ λ,*S*_{2}→ λ}),where

*S*∉*N*_{1}∪*N*_{2}. In this way,*G*generates the language*L*_{1}∪*L*_{2}.

The closure under concatenation is proven for the following four cases:

If λ ∉

*L*_{1}and λ ∉*L*_{2}, then let*G*= (*N*_{1}∪*N*_{2}∪ {*S*},*T, S, P*_{1}∪*P*_{2}∪ {*S*→*S*_{1}*S*_{2}}),where

*S*∉*N*_{1}∪*N*_{2}a new symbol.If λ ∈

*L*_{1}and λ ∉*L*_{2}, then let*G*= (*N*_{1}∪*N*_{2}∪ {*S*},*T, S, P**1*∪*P*_{2}∪ {*S*→*S*_{1}*S*_{2},*S*→*S*_{2}} \ {*S*_{1}→ λ}),where

*S*is a new symbol.If λ ∉

*L*_{1}and λ ∈*L*_{2}, then let*G*= (*N*_{1}∪*N*_{2}∪ {*S*},*T, S, P*_{1}∪*P*_{2}∪ {*S*→*S*_{1}*S*_{2},*S*→*S*_{1}} \ {*S*_{2}→ λ}),where

*S*∉*N*_{1}∪*N*_{2}a new symbol.If λ∈

*L*_{1}and λ ∈*L*_{2}, then let*G*= (*N*_{1}∪*N*_{2}∪ {*S*},*T, S*,*P*_{1}∪*P*_{2}∪ {*S*→*S*_{1}*S*_{2},*S*→*S*_{1},*S*→*S*_{2},*S*→ λ} \ {*S*_{1}→ λ,*S*_{2}→ λ}),where

*S*∉*N*_{1}∪*N*_{2}.

It can be easily seen that G generates the language *L*_{1}*L*_{2}.

Finally, let us consider the closure under Kleene-star. Let now *G*_{1} =
(*N*_{1}, *T, S*_{1}, *P*_{1})
and *G*_{2} = (*N*_{2}, *T, S*_{2},
*P*_{2}) be in Kuroda normal form and
generate the languages *L* (both *G*_{1} and *G*_{2})
such that *N*_{1} ∩ *N*_{2} =∅.

Let

G= (N_{1}∪N_{2}∪ {S, S'},

P_{1}∪P_{2}∪ {S→ λ,S→S_{1},S→S_{1}S_{2},S→S_{1}S_{2}S',S'→S_{1},S'→S_{1}S_{2},S'→S_{1}S_{2}S'} \ {S_{1}→ λ,S_{2}→ λ}),

where *S, S'* ∉ *N*_{1} ∪ *N*_{2},
they are new symbols. Then *G* generates the language *L*^{*}.

QED.

The closure of the class of context-sensitive languages under complementation was a famous problem and was open for more than 20 years. In the 1980's, Immerman, Szelepcsényi solved this problem independently. We present this result without proof.

**Theorem 29.** *The class of context-sensitive languages is closed under complementation.*

**Theorem 30.** *The class of context-sensitive languages is closed under intersection.*

**Proof.** The proof uses the fact that this class is closed both under union and complementation.
Let us consider the context-sensitive languages *L*_{1} and *L*_{2}.
Then, the complement of each of them is context-sensitive according to the theorem of Immerman
and Szelepcsényi. Their union is also context-sensitive, as we have proven constructively. The complement of this language is also context-sensitive.
However, this language is the same as *L*_{1} ∩ *L*_{2} by the De Morgan law.

QED.

**Exercise 75.** *Give a monotone grammar that generates the language of marked-copy:*

{

wcw∣w∈ {a,b}^{*}}

*over the alphabet* {*a,b,c*}. *(Hint: use context-sensitive rules to allow some nonterminals to terminate,
i.e., to change them to terminals only at the correct place.)*

**Exercise 76.** *Give context-sensitive grammars that generate the union and the concatenations
of the languages generated by grammars G*_{1} *and G*_{2}, *where*

G_{1}= ({S_{1},A_{1},B_{1},C_{1}}, {a,b,c},S_{1},

{S_{1}→ λ,S_{1}→C_{1}aA_{1},S_{1}→B_{1},aA_{1}→B_{1}B_{1},B_{1}→B_{1}b,B_{1}bb→cba,C_{1}→cA_{1}})and

G_{2}= ({S_{2},A_{2},B_{2},C_{2}}, {a,b,c},S_{2},

{S_{2}→cccS_{2}aA_{2}a,S_{2}→bA_{2},ccS_{2}→C_{2}bA_{2},bA_{2}→A_{2}b,A_{2}→cB_{2}C_{2}a,A_{2}→aa,cB_{2}→bB_{2},bB_{2}→baccabB_{2},C_{2}→C_{2}c,C_{2}c→A_{2}S_{2},C_{2}cc→cccc}).

**Exercise 77.** *Let*

G_{1}= ({S, A, B}, {0,1},S,

{_{S}→ λ,S→AB,A→ 0AB, 0A→ 1A,AB→ 11 })and

G_{2}= ({S, B, C, D}, {0,1},S,

{S→ λ,S→BC,S→D,B→BC,B→ 1, 1C→ 1D0,D→DD,D→ 11, 1D→C0,BDC→ 00D11 }).

*Give context-sensitive grammars that generate *

*L*(*G*_{1}) ∪*L*(*G*_{2}),*L*(*G*_{1})*L*(*G*_{2}),*L*(*G*_{2})*L*(*G*_{1}),(

*L*(*G*_{1}))^{*}and(

*L*(*G*_{2}))^{*}.

The word problem of context-sensitive grammars can be solved. Since this language class is accepted by linear bounded automata,
it can be solved in linear space in a nondeterministic manner. It is known that polynomial space is sufficient
with a deterministic algorithm: the required space is *c*∣*w*∣^{2},
where *c* is a constant and ∣*w*∣
is the length of the word. It is an open problem if linear space (i.e., *c* ∣*w*∣
with a constant *c*) is sufficient or not.
Regarding time complexity, there is no deterministic or nondeterministic algorithm is known that can solve the word problem
in polynomial time (for arbitrary context-sensitive grammar/language).

Now, we are going to present a naive solution to the word problem (which is very inefficient), but
at the same time it shows that the problem is solvable.
So let *G* = (*N, T, S, P*) and *w* be given.
If the input word is the empty word (*w* = λ), then it is in the language, if and only if
*S* → λ ∈ *P*.
If ∣*w*∣ > 0, then we may consider only the rules *u* → *v* of *P*
with the property ∣*u*∣ ≤ ∣*v*∣.
Then, let us use a bread-first search algorithm. Let the initial node of the graph be labeled by *S*.
Consider the productions as possible operators on the sentential forms. Then, the search-graph can be obtained by applying every
applicable rule for every node. This graph is usually infinite, but we need to obtain only a finite portion of it. (Every label must appear at most once in the graph.)
Since each of the rules has the monotone property we may cut those branches of the search-space that contain a longer sentential form than *w*
(the solution cannot be in the continuation of such a branch). When we have obtained all the portions of the search-graph representing sentential
forms not longer than *w*, then we can check whether *w* is a node of the graph, or not. If so, then it can be derived,
it is in the generated language, else it is not.

**Exercise 78.** *Check whether the words abc and ccc are in the language generated by the grammar*

G= ({S, A, B, C, D, E}, {a,b,c},S,

{S→ab,S→BS,S→ABS,A→a,A→BCE,AB→BA,B→b,BC→bc,CE→abc,D→b,ED→aE,E→DD,bA→SS}).