CS计算机代考程序代写 The Formal Statement of the Pumping Lemma and its Negation

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 ̸∈ L.
1