6
$\begingroup$

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.?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am unable to bring about connection between deterministic context free grammar and linear context free grammar, which one is subset of which? $\endgroup$ – anir123 Jan 21 '16 at 12:44
  • 1
    $\begingroup$ @Mahesha999 The families are incomparable: neither is included in the other. $\endgroup$ – Hendrik Jan Jan 21 '16 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.