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$ – David Richerby Apr 11 '17 at 11:09
  • 1
    $\begingroup$ @DavidRicherby Context-free, plus there is a grammar all (reachable, productive) sentential forms of which have at most one non-terminal. $\endgroup$ – 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$.

What is k?


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.