-1
$\begingroup$

enter image description here

(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?

$\endgroup$
2

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.