Pumping Lemma

Statement of Lemma

$\begin{aligned} &\forall A :\exists p \in \mathbb{N} : \\ &\exists xyz \in A : |xyz| \geq p \implies \\ &\forall i \in \mathbb{N} : xy^iz \in A \land \\ &|y| > 0 \land \\ &|xy| \leq p \end{aligned}$ - That is, $\{xz, xyz, xyyz\} \in A$

We “pump up” the number of occurances of y

Definitions

Take $M | L(M) = A$
Take $p = |M| = |Q|$
Take $s \in A = xyz : |s| \geq p$

Sketch of Proof

We note that $s$ visits states $p$ times.
- We make no claims about which states.
Define sequence of states $S = (q_0,s_1,s_2,\ldots,s_i,s_{i+1},\ldots,s_p)$
$\forall s_i \in S : s_i \in Q$
$p = |S| > |Q|$
$\therefore \exists i,j : s_i = s_j$

Find x,y,z

Let $x = (a_o,\ldots,a_{i-1})$
- $M$ is in state $s_j$ after reading $x$
Let $y = (a_i,\ldots,a_{j-1})$
- $M$ is in state $s_j$ after reading $y$ when beginning in $s_i$
- $s_i = s_j$
Let $z = (a_{j},\ldots,a_p)$
- $M$ accepts after reading $z$ when beginning in $s_j$

Pump on $y$

We note
- $xz$ is accepted by $(q_0,s_1,\ldots,s_i,s_{j+1},\ldots,s_p)$
  - Denote as $[0,i][j+1,p]$
- $xyz$ is accepted by $(q_0,s_1,\ldots,s_p)$
  - Denote as $[0,p] = [0,i][i+1,j][j+1,p]$

Pump on $y$

We note
- $xyyz$ is accepted by $(q_0,s_1,\ldots,s_{i+1},\ldots,s_{j-1},s_i\ldots,s_j, s_{j+1},\ldots, s_p)$
  - Denote as $[0,i][i+1,j][i+1,j][j+1,p]$
- $xy^nz$ is accepted by $[0,i][i+1,j]^n[j+1,p]$

Python

# assume S as a list of states.
S : List[states]
x : str
y : str
z : str
assert(states(x + z)         == S[:i] + S[j:]) 
assert(states(x + y + z)     == S    == S[:i]+S[i:j]+S[j:])
assert(states(x + y + y + z) == S[:i] + S[i:j] + S[i:j] + S[j:])
assert(states(x + y * 2 + z) == S[:i] + S[i:j] * 2      + S[j:])
# This can't run - it's infinite
assert(all((states(x+y*n+z) == A[:i]+A[i:j]*n+A[j:]) for n in count()))

Much easier with Pythonic slices.

Graphically

Show $s_i=s_j$

Label Edges

This is valid GNFA that reduces to a DFA.

Pumping Lemma

$\begin{aligned} &\forall A :\exists p \in \mathbb{N} : \\ &\exists xyz \in A : |xyz| \geq p \implies \\ &\forall i \in \mathbb{N} : xy^iz \in A \land \\ &|y| > 0 \land \\ &|xy| \leq p \end{aligned}$

Proof

Easy to read

$s \in A \land |s| > p$ requires
- $xy^nz \in A$
- $|y| > 0$
- $|xy| \leq p$

Pumping Lemma

Sketch

Preface

Avoid this trap

Example

Pumping Lemma

Statement of Lemma

Definitions

Sketch of Proof

Find x,y,z

Pump on $y$

Pump on $y$

Python

Graphically

Show $s_i=s_j$

Label Edges

Pumping Lemma

Easy to read

Examples

Irregular 0

Strategy

On Graphics

Irregular 1

Avoid this

Strategy

Combined Tactics

Irregular 2

Stretch Break