Notes - Models of Computation MT23, Pumping lemma

If $A$ is a regular language, then there is a number $p$ such that if $s \in A$ of length at least $p$, then $s$ may be divided into three pieces $s = xyz$ satisfying:

1. For each $i \ge 0$, $xy^i z \in A$ (i.e. we can pump up or down).
2. $ \vert y \vert > 0$
3. $ \vert xy \vert \le p$.

If for all $p \ge 1$, there exists $s \in L$ with $s \in L$ with $ \vert s \vert \ge p$ such that for all $x, y, z \in \Sigma^\star$ with $s = xyz$, $ \vert xy \vert \le p$, and $ \vert y \vert > 0$ there is an $i \ge 0$ such that $xy^i z \notin L$, then $L$ is not regular.

\[A \text{ regular} \implies \exists p \text{ s.t. } \forall s \in A, |s| \ge p, \exists x, y, z \in \Sigma^\star \text{ s.t. } s = xyz, |y| > 0, |xy| \le p \text{ and } \forall i \ge 0, xy^i z \in A\]

There exist languages that satisfy the pumping lemma but which are not regular.

(For example:)

\[L = \\{01^i01^j01^j \mid i, j > 0\\} \cup \\{w \in \\{0,1\\}^\star \mid w \text{ contains } 00\\}\]

If $L$ is a context-free language, then there exists some $p > 0$, such that if $w \in L$ and $ \vert w \vert \ge p$, then there exists $u,x,y,z$ such that:

• $w = uxyzv$
• $ \vert xz \vert > 0$
• $ \vert xyz \vert \le p$
• For all $i \ge 0$, $u x^i y z^i v \in L$

• $ \vert xz \vert > 0$
• $ \vert xyz \vert \le p$

You can remember it by contradiction. If the inequalities were the other way around, i.e.

• $ \vert xz \vert \le p$
• $ \vert xyz \vert > 0$

then just taking $x, z = \epsilon$ and having $y$ be bigger would mean that the pumping lemma was trivial (for any string $s$, take $u, x, z, w = \epsilon$ and $y = s$).

Take $p = \vert Q \vert + 1$ and consider any string of length $n \ge p$, say $w = x _ 1 \cdots x _ n \in L(M)$.

Use the notation $\hat \delta(q, a) := q’$ if the DFA is in state $q’$ after reading $a$.

By the pigeonhole principle, $\exists 1 \le i < j \le p$ such that $\hat \delta(q _ 0, x _ 1 \cdots x _ i) = \hat\delta(q _ 0, x _ 1 \cdots x _ j)$ (in any collection of more than $ \vert Q \vert $ states, we must have a repeated state somewhere).

Then let

\[\begin{aligned} &x = x_1 \cdots x_i \\\\ &y = x_{i+1} \cdots x_j \\\\ &z = x_j \cdots x_n \end{aligned}\]

Then

\[\hat \delta (q_0, xy) = \hat \delta(q_0, xy^i)\]

for all $i \ge 0$, so $xy^iz \in L(M)$ for all $i \ge 0$.

Todo, argument about parse trees.