#### Example

The example we want to show is non-regular is this one:L = { w ∈ {a,b}* : w = aWhat is it about this language which makes it non-regular? Imagine processing a string^{i}b^{i}, for some i ≥ 0 }

`w ∈ L`. As we see

`a`'s we would have to remember how many we've seen and then use that number to match off

`b`'s and accept if the numbers are equal. If we knew that there were, say, no more than 5

`a`'s, then the following DFA would serve (missing transitions go to dead states):

`a`'s we can remember. The idea is to make precise the finite memory limitation. It is done so by the following classical

*Pumping Lemma*.

### Pumping Lemma

Let `L` be a regular language,
then there is a `N > 0` which can be used as follows.

`w ∈ L`such that

`|w| ≥ N`,

`w`can be written as

w = xyzsuch that:

`y ≠ ε``|xy| ≤ N``xy`, for all^{i}z ∈ L`i ≥ 0`

**Proof:**

`M`, for

`L`. Let

`N`= the number of states. Take a string

`w`, let

`n = |w|`and assume

`n ≥ N`. Write

`w = σ`and consider the transitions which would occur when processing

_{1}...σ_{n}`w`from start state

`q`:

_{0}δ(qConsider the_{0},σ_{1}) = q_{1}, δ(q_{1},σ_{2}) = q_{2}, ..., δ(q_{n-1},σ_{n}) = q_{n}∈ F

`N+1`states

`{q`related to the first

_{0},q_{1},...,q_{N}}`N`transitions. Here is a depiction:

`q`, where

_{i}= q_{j}`0 ≤ i < j ≤ N`. Then write

`w = xyz`where

(qThe substring_{0},xyz) ⊢* (q_{i},yz) ⊢* (q_{j},z) ⊢* (q_{n},ε)

`y`makes the transition from

`q`to

_{i}`q`, where

_{j}`i < j`, and so

`|y| > 0`. Write

`q = q`as the common value. Here is a depiction:

_{i}= q_{j}`q`'s substitution gives:

(qand so we can "pump" the substring_{0},xyz) ⊢* (q,yz) ⊢* (q,z) ⊢* (q_{n},ε)

`y`, looping from

`q`back to itself any number of times:

(q,yThus,^{i}z) ⊢* (q,z), for all i ≥ 0

(qmeaning that_{0},xy^{i}z) ⊢* (q,y^{i}z) ⊢* (q,z) ⊢* (q_{n},ε), for all i ≥ 0

`xy`is accepted for all

^{i}z`i ≥ 0`. ■

#### Common Proofs

The result of the pumping lemma says thatw = xyz and xyYou want to create a false statement due to the extra inclusions in^{i}z ∈ L

`L`, and usually you can generate the false statement by one of these two statements:

xz ∈ L (i = 0) xyyz ∈ L (i = 2)

### Classic non-regular example

The proof of non-regularity of a language using the pumping lemma is a proof by contradiction. The goal is to assume that the language is regular and then derive strings which are not in the language, thereby contradicting the regularity assumption.**This language is not regular**:

LSuppose this were regular. Let_{0}= { w ∈ {a,b}* : w = a^{i}b^{i}, for some i ≥ 0 }

`N`be the constant selected by the pumping lemma. Consider the string

`w = a`. Then

^{N}b^{N}`|w| = 2·N > N`, and so we can write

`w = xyz`according to the consequences of the lemma. Since

`|xy| ≤ N`and

`|y| > 0`, it must be that

`y`is a non-empty substring of the

`a`part, i.e.

^{N}`y = a`for some

^{k}`k > 0`. According to the pumping lemma,

`xyyz = a`must also belong to

^{N+k}b^{N}`L`for

`k > 0`, a contradiction.

### Related non-regular languages

**These languages are not regular**:

L = { w ∈ {a,b}* : w = aFrom the given^{m}b^{n}, for m > n } L = { w ∈ {a,b}* : w = a^{m}b^{n}, for m < n }

`N`, use this as the string in the former:

w = aand this in the latter:^{N+1}b^{N}

w = a^{N}b^{N+1}

**This language is not regular**:

L = { w ∈ {a,b}where^{*}: #_{a}(w) = #_{b}(w) }

`#`is the number of occurrences of

_{σ}(w)`σ`in

`w`. For a slightly different approach, this proof by contradiction relies on the previous example and closure properties. If

`L`were regular then, since

`a*b*`is regular, this language would also have to be regular:

L ∩ a*b* = { w ∈ {a,b}* : w = aWe just proved the non-regularity of^{i}b^{i}, for some i ≥ 0 } = L_{0}

`L`, which is a contradiction. Therefore

_{0}`L`cannot be regular.

**This language is not regular**:

L = { w·wThis is the set of all even-length palindromes. One approach is to simplify by restricting the possibilities as we did Consider:^{R}: w ∈ {a,b}* }

L ∩ a*bba*Try completing the argument.