8 votes

Closure properties of linear context-free languages

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 ...
user avatar
  • 27.7k
5 votes
Accepted

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

Let $\cal F$ and $\cal G$ be two classes of grammars, or what ever language defining devices you want. We assume that $L({\cal F}) \subset L({\cal G})$, the languages defined by the first class are ...
user avatar
  • 27.7k
4 votes
Accepted

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

Consider this string: $w=a^kb^ka^{2k+2k!}b^ka^k$. We will show that we can't write this string in form of $uvxyz$ in a way that the conditions of pumping lemma for linear languages statisfy. Because $|...
user avatar
3 votes

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

In addition to reasons of curiosity and unveiling structure, there are practical benefits. As concrete examples, linear grammars are easier to prove correct, are easier to parse for and always have ...
user avatar
  • 71k
2 votes
Accepted

Greibach Normal Form of Linear Language

As you note, the problem is with the productions of the form $A\to Ba$. Consider a sequence of such productions $A_0\to A_1 a_1$, $A_1\to A_2 a_2$, $\dots$, $A_{n-1}\to A_n a_n$, $A_n\to bB$, where ...
user avatar
  • 27.7k
2 votes

Pumping lemma for linear languages

Study the proof of the pumping lemma for context-free languages. The pumping property is obtained by finding a repeated non-terminal on a path in the derivation tree. By looking at the first ...
user avatar
  • 27.7k
1 vote

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

Let $p$ be the constant promised by the pumping lemma. Without loss of generality, $p \geq 2$. Let $w = 0^p 1 0^{2p+p!} 1 0^p$. Since the left half of $w$ is $0^p10^{p+p!/2}$ and the right half of $w$ ...
user avatar
1 vote

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

As @vonbrand pointed out, there are context-free languages that do not have any linear context-free grammars. According to this source, one concrete example is $\{a^i b^i a^j b^j | i, j \in \mathbb{N} ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible