Day 10

This class will discuss the pumping lemma for regular expressions.

---

Let $A$ be a regular language. There exists some natural number $p$ (pumping length) such that for every string $w\in A^{\ast }$ the following holds:

$$|w|\ge p$$

divide $w$ into three parts:

$$w=xyz$$

such that:

$$\begin{array}{r}\mid xy\mid \le p\\ \mid y\mid \ge 1\\ \forall i\ge 0:x{y}^{i}z\in A\end{array}$$

---

Pumping Lemma for Regular Languages

For the pumping lemma for regular languages, we have a regular language $L$ and a pumping length $p$ such that for all strings $w\in L$ with $|w|\ge p$, we can divide $w$ into three parts $w=xyz$ such that: