Skip to main content

Questions tagged [linear-languages]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer

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 ...
Knogger's user avatar
  • 1,292
2 votes
1 answer

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 ...
ErroR's user avatar
  • 1,942
2 votes
1 answer

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 ...
LeviathanTheEsper's user avatar
2 votes
2 answers

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$ ...
User584322's user avatar
3 votes
1 answer

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 ...
Arka Pal's user avatar
  • 311
2 votes
3 answers

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 ...
mavavilj's user avatar
  • 579
6 votes
1 answer

Closure properties of linear context-free languages

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}...
anand nayak's user avatar