<p>A <strong>linear grammar</strong> is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.
A <strong>linear language</strong> is a language generated by some linear grammar.<br>
See also:  <a href="https://en.wikipedia.org/wiki/Linear_grammar" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Linear_grammar</a></p>

<ul>
<li>It is known that the regular languages form a proper subfamily of the linear languages, and that the linear languages form a proper subfamily of the context-free languages.</li>
<li>The language $\{a^kb^kc^nd^n|k,n\ge1\}$ is known to be context-free but not linear.</li>
</ul>

<p>The text-book <em>"Introduction to Automata Theory, Languages, and Computation"</em> by John E. Hopcroft and Jeffrey D. Ullman (Addison-Wesley, 1979) states a pumping lemma for linear languages:</p>

<blockquote>
  <p>Let $L$ be a linear language.
  Then there exists an integer $n$ such that for any word $p\in L$ with $|p|\ge n$, there exists a factorization $p=uvwxy$ with the following properties: </p>
  
  <ol>
  <li>$uv^iwx^iy \in L$ for all integers $i\in\mathbb{N}$</li>
  <li>$|vx|&gt;0$</li>
  <li>$|uvxy| \le n$.</li>
  </ol>
</blockquote>

CC BY-SA 3.0
2017-02-07T18:32:00.213Z
Thanks. While we're at it, how does one prove that a given CFL is non-linear? The general decision problem is not Turing-computable, but the Dyck language of balanced parentheses is known to be not linear. How?
Aryeh
CC BY-SA 3.0
2017-02-07T18:45:39.017Z
Many thanks, I'd upvote again if I could.
Aryeh
CC BY-SA 3.0
2017-02-07T18:23:50.580Z
2017-02-07T18:43:04.423Z
2017-02-07T18:43:04.423Z
Gamow
<p>Consider Context-Free Grammars with rules of the form $S\to\epsilon$
or $A\to aB | Ba|a$,
meaning that any nonterminal other than $S$ can be replaced by a terminal, or by a pair of letters exactly one of which is nonterminal (and the other one terminal). What class of languages do such grammars generate? Certainly the regular ones, but also $a^n b^n$, via the rules $S\to\epsilon|aB$, $B\to b|Ab$, $A\to a|aB$. Short of a full characterization, I conjecture that these grammars do <em>not</em> generate the full CFL language family, and would be curious to see a proof.</p>

CC BY-SA 3.0
2017-02-07T17:28:04.920Z
You should google for "linear language" or "linear context-free grammar".
Gamow
CC BY-SA 3.0
2017-02-07T18:15:02.053Z
@Gamow this appears to be exactly what I was looking for. If you make it into a full answer, I'll accept.
Aryeh
<fl.formal-languages><automata-theory>
CFGs in a certain normal form
Aryeh
# CFGs in a certain normal form

(Asked by: username_0 on 2017-02-07)

Consider Context-Free Grammars with rules of the form $S\to\epsilon$
or $A\to aB | Ba|a$,
meaning that any nonterminal other than $S$ can be replaced by a terminal, or by a pair of letters exactly one of which is nonterminal (and the other one terminal). What class of languages do such grammars generate? Certainly the regular ones, but also $a^n b^n$, via the rules $S\to\epsilon|aB$, $B\to b|Ab$, $A\to a|aB$. Short of a full characterization, I conjecture that these grammars do *not* generate the full CFL language family, and would be curious to see a proof.

**Tags:** fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: You should google for "linear language" or "linear context-free grammar".  
> **username_0**: @Gamow this appears to be exactly what I was looking for. If you make it into a full answer, I'll accept.  

---

## 1 answers

### Answer by username_1 on 2017-02-07. Score: 5 | Accepted answer

A **linear grammar** is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.
A **linear language** is a language generated by some linear grammar.  
See also: <https://en.wikipedia.org/wiki/Linear_grammar>

* It is known that the regular languages form a proper subfamily of the linear languages, and that the linear languages form a proper subfamily of the context-free languages.
* The language $\{a^kb^kc^nd^n|k,n\ge1\}$ is known to be context-free but not linear.

The text-book *"Introduction to Automata Theory, Languages, and Computation"* by John E. Hopcroft and Jeffrey D. Ullman (Addison-Wesley, 1979) states a pumping lemma for linear languages:

> Let $L$ be a linear language.
> Then there exists an integer $n$ such that for any word $p\in L$ with $|p|\ge n$, there exists a factorization $p=uvwxy$ with the following properties:
>
> 1. $uv^iwx^iy \in L$ for all integers $i\in\mathbb{N}$
> 2. $|vx|>0$
> 3. $|uvxy| \le n$.

> **Comments:**
> **username_0**: Thanks. While we're at it, how does one prove that a given CFL is non-linear? The general decision problem is not Turing-computable, but the Dyck language of balanced parentheses is known to be not linear. How?  
> **username_0**: Many thanks, I'd upvote again if I could.  

---

