# Questions tagged [linear-languages]

The tag has no usage guidance.

7 questions
Filter by
Sorted by
Tagged with
62 views

### Is there a linear language $L$ such that $\overline{L} \in \texttt{Type-2} \setminus \texttt{Lin}$?

This question is kind of a follow-up to a question asked a few days ago. Both of the non-linear complements of linear languages found were also not context free. So the question is this: Is there some ...
• 1,292
148 views

### The complement of a particular language

We know that Linear context-free languages are not closed under complement, so I encountered a challenge in finding an example to show the above theorem. I think the complement of $L={a^nb^n}$ is not ...
• 1,942
67 views

### Greibach Normal Form of Linear Language

I was trying to get an arbitrary linear language to its GNF, and I converted it into one where all the productions were of the form $A\to Ba, A\to aB, A\to a$. In this question, the accepted answer ...
124 views

### Prove $\{xy \mid |x|=|y|, x \neq y\}$ is not a linear language

Show the language $$L = \{xy \mid |x| = |y|, x\neq y\}$$ is not linear. I've seen and proved a pumping lemma for linear languages, mentioned here: If $L$ is linear then there exists a constant $p$ ...
2k views

### Pumping lemma for linear languages

Let $L$ be a linear language. Then there is a constant $p$ such that for all $w$ in $L$ with $|w| \ge p$, $w$ can be written as $uvxyz$ where (i) $|uvyz| \le p$ (ii) $|vy| > 0$ (iii) $uv^ixy^iz$ is ...
• 311
3k views

### Why is the distinction between linear and context-free grammars useful?

The linear grammar is a grammar that's either left, right or left and right linear. The context-free grammar can contain any kind of productions of non-terminals and terminals. All linear grammars ...
• 579
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}...