(from 'An Introduction to Formal Languages and Automata' by Peter Linz)
What I do not understand, is why we have done our best to make sure that the condition (8.2) holds. Why is this restriction important/useful?
2
-
$\begingroup$ This problem was also considered elsewhere, see What's the reason for the second condition of the pumping lemma(s)?. Perhaps its answers are helpful. $\endgroup$– Hendrik JanAug 14, 2022 at 23:50
-
$\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. $\endgroup$– D.W. ♦Aug 15, 2022 at 4:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The restriction is definitely useful. It provides you with an additional guarantee on the structure of the decomposition of $w$, which you can exploit in your proofs.
For example the language $L = \{a^n b^k c^n d^k \mid n, k \ge 0\}$ is not context-free and a possible proof using the pumping lemma is as follows: suppose that $L$ is context free, and let $m$ be its pumping length. Consider the word $w=a^m b^m a^m b^m$. The pumping lemma ensures that there is a decomposition of $w = uvxyz$ with $|vxy| \le m$, and this implies that $vxy$ cannot contain both a $a$ and a $c$, nor both a $b$ and a $d$. As a consequence $uv^2xy^2z \not\in L$, which provides the sought contradiction.
Notice that the above proof would not work without using $|vxy| \le m$, since we could pick $u=a^{m-1}$, $v=a$, $x=b^m$, $y=c$, and $z=c^{m-1}d^k$, which satisfies $uv^i x y^i z \in L$ for all $i \in \mathbb{N}$.
