Closure properties of linear context-free languages

Question

Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages. Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, $\overline{L_1}$, $L_1 . L_2$, etc.?

Answer 1

For our readers. Linear grammars are close to regular grammars, a single nonterminal at the time, but they may generate letters at both sides $A \to aBb$ with $A,B$ nonterminal, and $a,b$ terminal (or empty). $REG \subset LIN \subset CF$, strict. Some closure proofs may benefit from another way to define linear languages: as single turn pushdown languages.

Linear languages are closed under union, construction as for context-free grammars $S\to S_1, S\to S_2$. Likewise they are closed under intersection with regular languages.

They are not closed under intersection: $\{ a^n b^n c^m \mid m,n \ge 0 \} \cap \{ a^n b^m c^m \mid m,n \ge 0 \}$.

Hence they cannot be closed under complement, but I would be nice to have a concrete example.

Neither are they closed under concatenation, intuitively because $S\to S_1S_2$ is not a linear structure. Same for Kleene star.

Linear languages have a pumping property which is similar to that of the context-free languages, except that the composition $z = uvwxy$ may additionally be required to have $|uvxy|\le m$, where $m$ is the pumping constant. This is similar to the requirement for regular languages, where pumping may be assumed to be at the beginning. Linear languages also have a linear structure (like finite state computations) but the symbols that are generated first are at both ends of the string. WIth this property it can be easily shown that $K =\{a^nb^n \mid n\ge 1\}^2$ is not linear.

Both regular and context-free are closed under rotation, but linear languages are not: $K$ is the rotation of linear $\{ b^m a^n b^n a^m \mid m,n\ge 1 \}$ (and a suitable regular intersection).

Regular languages are closed under quotient, but linear (and context-free) languages are not. In fact the operation is very powerful: the RE languages are quotients of two linear languages.

On the other hand, they are closed under quotient with regular languages. That follows as they form a full trio (i.e., they are closed under homomorphisms, and inverse morphisms and intersection with regular languages). Consequently/equivalently they are closed under finite state transductions.

Of course, they are closed under reversal.