Pumping Lemma Game
Proving Non-Regularity
For all $n$ there exists $z$ longer than $n$, such that for all ways of writing $z=uvw$ where:
- $\vert uv\vert\leq n$
- $\vert v\vert\geq 1$
- For all $i\geq0$, the string $uv^iw$ is not in $L$.
This is a Ehrenfeucht-Fraïssé game between two players:
- Adam (for all)
- Eve (exists)
| Round | Adam | Eve |
|---|---|---|
| 1 | Chooses $n$ | Chooses $z\in L(\vert z\vert >n)$ |
| 2 | Writes $z=uvw$ $(\vert uv\vert \leq n,\vert v\vert\geq1)$ | Chooses $i$ |
Eve wins if $uv^iw\notin L$ otherwise Adam wins.
Eve needs to give a strategy that, regardless of what Adam does, she always wins the game.
Example
We will use our non-regular language as an example:
\[L_0=\{0^n1^n\vert n\geq0\}\]| Round | Adam | Eve |
|---|---|---|
| 1 | Chooses $n$ | Chooses $z=0^n1^n\in L_0$ |
| 2 | Writes $z=uvw$ as below: | Chooses $i=2$ |
Adam is able to choose this string in the language:
\[\underbrace{00000000}_u\underbrace{00}_v\underbrace{001111111111}_w\]The $i=2$ constraint from eve produces this string which is not in the language, which means eve wins:
\[\underbrace{00000000}_u\underbrace{00}_v\underbrace{00}_v\underbrace{001111111111}_w\]- $uv^2w=0^{n+k}1^n\notin L_0$
- Where $k=\vert v\vert$.
Eve winning means that this is not a regular language.
There are several more examples in this video.