HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

General version of pumping lemma for regular languages, how many partitions to consider

Submitted by: @import:stackexchange-cs··
0
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$?

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.

Context

StackExchange Computer Science Q#93205, answer score: 3

Revisions (0)

No revisions yet.