In this section we show that the class of linear languages is closed under union, but it is not closed under other regular operations and under other set-theoretical operations.

**Theorem 13.** *The class of linear languages is closed under union, i.e., the union of any two linear
languages is also linear.*

**Proof.** The proof is constructive. Let *L*_{1} and
*L*_{2} be linear languages.
Let the linear grammars *G*_{1} = (*N*_{1}, *T*,
*S*_{1}, *P*_{1}) and
*G*_{2} = (*N*_{2}, *T*, *S*_{2},
*P*_{2}) generate the languages *L*_{1} and *L*_{2}
such that *N*_{1} ∩ *N*_{2} = ∅
(this can be done by renaming nonterminals of a grammar without affecting the generated language). 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}, is a new symbol.
It can be seen that *G* generates the language *L*_{1} ∪ *L*_{2}.

QED.

**Theorem 14.** *The class of linear languages is not closed under concatenation and Kleene-star.*

Instead of a formal proof we offer a suggestion:

Let us consider the language

L= {a∣^{n}b^{n}n> 0}.

The languages *L* · *L* and *L*^{*} are not linear languages.

**Theorem 15.** *The class of linear languages is not closed under complement and intersection.*

**Proof.** Let us start with the intersection. Observe that both of the languages

L_{1}= {a∣^{j}b^{j}c^{k}j, k∈ ℕ} andL_{2}= {a∣^{k}b^{j}c^{j}j, k∈ ℕ}

are linear. The intersection of these two languages is

L=L_{1}∩L_{2}= {a∣^{j}b^{j}c^{j}j∈ ℕ}.

As we will prove it in Example this language is not context-free, and therefore it is not linear. This proves the non closure under intersection.

We are going to prove now that the class is not closed under complement. Consider
the following language: {*wcw*∣*w* ∈ {*a,b*}^{*}}
over the alphabet {*a,b,c*}.
It is called the language of ''marked-copy''. In Example 43. we prove that this language is not context-free,
and thus it is not linear. However, the complement of this language is a linear language.

QED.

**Exercise 53.** *Give a linear grammar that generates the complement of the language of marked-copy.
Hints: it can be done as union of linear languages. A word can be in this complement if, *

*it does not contain any c,**it does contain at least two c's,**it is of the form u c v, with u,v*∈ {*a,b*}^{*}, but ∣*u*∣≠∣*v*∣,*it is of the form u c v, with u,v*∈ {*a,b*}^{*},*and*∣*u*∣=∣*v*∣,*but there is a mismatch letter: u*=*u*_{1}*xu*_{2}*and v*=*u*_{1}yu*2*,*where x,y*∈ {*a,b*},*but x*≠*y*.

**Exercise 54.** *Give a grammar that generates the union of the languages generated by grammars
G*_{1} *and G*_{2}, *where*

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

{S_{1}→aaS_{1}ccc,S_{1}→A_{1},A_{1}→bB_{1}b,B_{1}→bB_{1},B_{1}→b})

*and *

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

{S_{2}→cccS_{2}aa,S_{2}→bA_{2},A_{2}→A_{2}b,A_{2}→cB_{2}aa,A_{2}→C_{2},B_{2}→bB_{2},B_{2}→baccab,C_{2}→C_{2}c,C_{2}→A_{2}}).