# Pumping lemma for linear languages

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.

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

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$.