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 L1 and L2 be linear languages. Let the linear grammars G1 = (N1, T, S1, P1) and G2 = (N2, T, S2, P2) generate the languages L1 and L2 such that N1 ∩ N2 = ∅ (this can be done by renaming nonterminals of a grammar without affecting the generated language). Then, let
G = (N1 ∪ N2 ∪ {S}, T, S, P1 ∪ P2 ∪ {S → S1, S → S2}),
where S ∉ N1 ∪ N2, is a new symbol. It can be seen that G generates the language L1 ∪ L2.
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 = {anbn∣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
L1 = {aj bjck∣j, k ∈ ℕ} and L2 = {akbjcj∣j, k ∈ ℕ}
are linear. The intersection of these two languages is
L = L1 ∩ L2 = {ajbjcj∣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 = u1xu2 and v = u1yu2, where x,y ∈ {a,b}, but x ≠ y.
Exercise 54. Give a grammar that generates the union of the languages generated by grammars G1 and G2, where
G1 = ({S1, A1, B1}, {a,b,c}, S1,
{ S1 → aaS1ccc,
S1 → A1,
A1 → bB1b,
B1 → bB1,
B1 → b
})and
G2 = ({S2, A2, B2, C2}, {a,b,c}, S2,
{ S2 → cccS2aa,
S2 → bA2,
A2 → A2b,
A2 → cB2aa,
A2 → C2,
B2 → bB2,
B2 → baccab,
C2 → C2c,
C2 → A2
}).