137 views
0 votes
0 votes
Prove the following generalization of the pumping lemma.
If $L$ is regular, then there exists an $m$, such that the following holds for every sufficiently long $w ∈ L$ and every one of its decompositions $w = u_1υu_2$, with $u_1,u_2 ∈ Σ^*, |υ| \geq m.$ The middle string $υ$ can be written as $υ = xyz,$ with $|xy| ≤ m, |y| ≥ 1,$ such that $u_1xy^izu_2 ∈ L$ for all $i = 0,1, 2,….$

Please log in or register to answer this question.

Related questions