# 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.
• The language $\{a^kb^kc^nd^n|k,n\ge1\}$ is known to be context-free but not linear.
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$.