HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Pumping lemma for linear languages

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
linearlanguagespumpingforlemma

Problem

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.

Solution

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?

Context

StackExchange Computer Science Q#73791, answer score: 3

Revisions (0)

No revisions yet.