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.

  • 4
    $\begingroup$ You should google for "linear language" or "linear context-free grammar". $\endgroup$ – Gamow Feb 7 '17 at 17:28
  • 1
    $\begingroup$ @Gamow this appears to be exactly what I was looking for. If you make it into a full answer, I'll accept. $\endgroup$ – 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.
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$.
  • 1
    $\begingroup$ 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? $\endgroup$ – Aryeh Feb 7 '17 at 18:32
  • 1
    $\begingroup$ Many thanks, I'd upvote again if I could. $\endgroup$ – Aryeh Feb 7 '17 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.