# CFGs in a certain normal form

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.

• You should google for "linear language" or "linear context-free grammar". – Gamow Feb 7 '17 at 17:28
• @Gamow this appears to be exactly what I was looking for. If you make it into a full answer, I'll accept. – Aryeh Feb 7 '17 at 18:15

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.

• 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$.
• 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 Feb 7 '17 at 18:32
• Many thanks, I'd upvote again if I could. – Aryeh Feb 7 '17 at 18:45