patternMinor
General version of pumping lemma for regular languages, how many partitions to consider
Viewed 0 times
versionlanguagesregularconsidergeneralpumpingpartitionsforlemmahow
Problem
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$?
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$?
Solution
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.
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.
Context
StackExchange Computer Science Q#93205, answer score: 3
Revisions (0)
No revisions yet.