Let $L$ be a linear language. Then there is a constant $p$ such that for all $w$ in $L$ with $|w| \ge p$, $w$ can be written as $uvxyz$ where (i) $|uvyz| \le p$ (ii) $|vy| > 0$ (iii) $uv^ixy^iz$ is in $L$, for all $i \ge 0$. How do I prove the first condition? I am having difficulty proving the bound and relating the bound k to the grammar.

  • 5
    $\begingroup$ What's a linear language? What did you try? Where did you get stuck? Do your course materials or textbooks cover this material? $\endgroup$ Commented Apr 11, 2017 at 11:09
  • 2
    $\begingroup$ @DavidRicherby Context-free, plus there is a grammar all (reachable, productive) sentential forms of which have at most one non-terminal. $\endgroup$
    – Raphael
    Commented Apr 15, 2017 at 10:59

1 Answer 1


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 repetition you can find a bound on the length of that path in the tree, and hence a bound on the length of the substring $uvyz$.

What is k?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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