Es seien ´L_1´ und ´L_2´ zwei lineare Sprachen, die von den linearen Grammatiken ´G_1 = (N_1, T, P_1, S_1)´ und ´G_2 = (N_2, T, P_2, S_2)´ mit ´N_1 nn N_2 = O/´ erzeugt werden. Dann erzeugt

´G = (N_1 uu N_2 uu {S}, T, {S -> S_1, S -> S_2} uu P_1 uu P_2, S)´

die Vereinigung und ist linear.

Die Menge der linearen Sprachen ist also unter Vereinigung abgeschlossen.

Durchschnitt: Es wurde gezeigt, dass der Durchschnitt der kontextfreien Sprachen ´L_1 = {a^n b^m c^m | n, m >= 1}´ und ´L_2 = {a^n b^n c^m | n, m >= 1}´ die Sprache ´{a^n b^n c^n | n >= 1}´ ergibt, die nicht kontextfrei und damit auch nicht linear ist. Daher reicht es zu zeigen, dass ´L_1´ und ´L_2´ linear sind. Dies ist gegeben, da die linearen Grammatiken

´G_1 = ({S,A}, {a,b,c}, {S -> aS, S -> aA, A -> bAc, A -> bc}, S)´

und

´G_2 =({S,A}, {a,b,c}, {S -> Sc, S -> Ac, A -> aAb, A -> ab}, S)´

die Sprachen ´L_1´ (da jede Ableitung die Form

´S => aS => a^2 S => … => a^(n−1) S => a^nA => a^nbAc => … => a^n b^(m−1) Ac^(m−1) => a^n b^m c^m´

hat) und ´L_2´ (mit analoger Begründung) erzeugen. Die Menge der linearen Sprachen ist also unter Durchschnitt nicht abgeschlossen.

Komplement: Wäre Abschluss unter Komplement für lineare Sprachen gegeben, so wäre unter Beachtung der Abgeschlossenheit unter Vereinigung auch ´C(C(L_1) uu C(L_2)) = L_1 nn L_2´ linear (wobei ´L_1´ und ´L_2´ die beim Durchschnitt betrachteten Sprachen sind). Dies ist aber falsch. Die Menge der linearen Sprachen ist also unter Komplement nicht abgeschlossen.

Produkt: Die Sprache ´L = {a^n b^n | n >= 1}´ ist linear, da sie von ´({S}, {a, b}, {S -> aSb, S -> ab}, S)´ erzeugt wird. Aber das Produkt ´L * L = {a^n b^n a^m b^m | n, m >= 1}´ ist nicht linear (siehe Aufgabe 1 dieser Serie). Die Menge der linearen Sprachen ist also unter Produkt nicht abgeschlossen.

Kleene-Abschluss: Wir wählen wieder ´L = {a^n b^n | n >= 1}´. Mittels Schleifensatz lässt sich nun wie in Aufgabe 1 nachweisen, dass ´L^(**)´ nicht linear ist, da das Wort ´a^(2k) b^(2k) a^(2k) b^(2k) in L^2 sube L^(**)´ in ´L^(**)´ liegt. Die Menge der linearen Sprachen ist also unter Kleene-Abschluss nicht abgeschlossen.