pumping_negated.dvi
The Formal Statement of the Pumping Lemma and its Negation
The pumping lemma states that for any regular language L, there is a positive integer p such that
for any string s in the language L with the length of s greater than or equal to p there are three
strings x, y, z such that s = xyz with the length of xy less than or equal to p and the length of y
strictly positive such that for any natural number i the string xyiz is in L.
In symbols this is written, for L a regular language
∃p.(p > 0) ∧ ∀s.(s ∈ L ∧ |s| ≥ p) ⇒ ∃x, y, z.(s = xyz ∧ |xy| ≤ p ∧ |y| > 0 ∧ ∀i.xyiz ∈ L).
We negate this in stages as follows:
¬[∃p.(p > 0) ∧ ∀s.(s ∈ L ∧ |s| ≥ p) ⇒ ∃x, y, z.(s = xyz ∧ |xy| ≤ p ∧ |y| > 0 ∧ ∀i.xyiz ∈ L)].
which is
∀p.¬(p > 0) ∨ ¬[∀s. . . .]
Before we delve any deeper, recall that P ⇒ Q is the same as ¬P ∨ Q so in the above we can
write
∀p.(p > 0) ⇒ ¬[∀s. . . .].
Using this conversion to implication gives something more readable, though it may confuse those
who expect to see the ands become ors. Similarly ¬(P ⇒ Q) = ¬(¬P ∨ Q) = P ∧ ¬Q. Now we
can look deeper into the expression and we get
∀p.(p > 0) ⇒ ∃s.(s ∈ L) ∧ (|s| ≥ p) ∧ ¬[∃x, y, z.(s = xyz ∧ |xy| ≤ p ∧ |y| > 0) ∧ ∀i.xyiz ∈ L].
Then pushing the negation further inside we get
∀p.(p > 0) ⇒ ∃s.(s ∈ L) ∧ (|s| ≥ p) ∧ ∀x, y, z.(s = xyz ∧ |xy| ≤ p ∧ |y| > 0) ⇒ ¬[∀i.xyiz ∈ L].
Finally,
∀p.(p > 0) ⇒ ∃s.(s ∈ L) ∧ (|s| ≥ p) ∧ ∀x, y, z.(s = xyz ∧ |xy| ≤ p ∧ |y| > 0) ⇒ ∃i.xyiz 6∈ L.
1