4
$\begingroup$

The pumping lemma for regular languages states, that one should consider a string $w = xyz, w\in L$, that is, every possible division of $w$ into $xyz$.

The article on wikipedia says, that this version is a special case of a more general version, in which one should consider strings $uwv = uxyzv$.

When using that general version of the lemma, does it require considering every possible partition of the string into $uxyzv$? I.e. does it require considering every possible $u$ and $v$?

$\endgroup$
3
$\begingroup$

The general version of the Pumping Lemma specifically applies to all strings $uwv \in L$ such that the length of $w$ is greater than or equal to a certain constant (the pumping length). No matter what $u$ and $v$ you pick, so long as whatever's between them is long enough, the general version will work.

So you don't need to consider all $u$ and $v$, only the ones that are useful to solving your problem. For instance, if you have the language $0^a 1^b 2^b 3^c$ where $a$, $b$, $c$ are positive integers, you can let $u$ be the string of zeroes at the beginning, let $v$ be the string of threes at the end, and then apply the simpler version of the lemma to the remaining part.

Conversely, the choice of $x$, $y$, and $z$ is harder, because the lemma doesn't guarantee that it works for all choices of these substrings, only for at least one choice of them.

$\endgroup$

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.