## Regular Expressions

• Consider these languages over Σ = {0, 1}
• B = {0n1n | n ≥ 0}

• C = {w | w has an equal number of 0s and 1s}

• D = {w | w has an equal number of occurrences of 01 and 10 as substrings} (example: 010 ∈ D)

• Which are regular?

• How do we PROVE that a language is regular?
• How do we PROVE that a language is NOT regular?

## Pumping Lemma: Purpose

• Tool for showing that a language is NOT REGULAR
• ie that it's impossible to create a FSM for the language

• Basic technique: Contradiction: assume lang is regular and get a contradiction

• We will prove all Regular Languages have the pumping property

• To show that a language is not regular we ...

## Pumping Lemma for Regular Languages: Introduction

• We start by proving that ALL regular languages have a pumping property (ie prove the pumping lemma)

• Then, to show that language L is not regular, we show that L does NOT have the pumping property.
• L regular implies L has pumping property
• L not have pumping property implies L not regular

• Pumping property: All strings in the language that are longer than the pumping length have a section that can be repeated any number of times to create new strings in the language

• We will also see a Pumping Lemma for Context Free Languages

## Pumping Lemma for Regular Languages: Theorem 1.70

• If A is a regular language, then
• there is a number p (the pumping length) where,
• if s is any string in A of length at least p (ie sA and |s| ≥ p), then
• s may be divided into three pieces, s = xyz, and
• s satisfies the following conditions:
1. for each i ≥ 0, xyizA

2. |y| > 0 (ie y ≠ ε)

3. |xy| ≤ p

## Pumping Lemma for Regular Languages: In Different Words

• If A is a regular language, then

• p ∈ Integers such that ∀sA with |s| ≥ p,

• x, y, z such that

1. s = xyz

2. xyizA, ∀i ≥ 0,

3. |y| > 0

4. |xy| ≤ p

## Negating the Pumping Lemma Conditions

• When using the PL to show that language is NOT regular,
• We assume the language is Regular and show that the PL does not hold

• To show that the PL does not hold we
• Find a string s with |s| ≥ p, for which
• There are NO strings x, y, z for which the conditions hold
• In other words, for every s = xyz, one or more of conditions 1, 2, or 3 is violated
• In other words, for every way of dividing s into xyz, one or more of conditions 1, 2, or 3 is violated

• You only need one such string since the PL says that the conditions hold ∀s with |s| ≥ p

## Pumping Lemma Conditions: What they mean

1. s can be divided in 3 substrings, x, y, z

2. for each i ≥ 0, xyizA: pumping the loop produces strings that are in the language

3. |y| > 0: the pumped section is not empty (ie, if y = ε, then the Lemma is meaningless))

4. |xy| ≤ p: a loop must appear within the first p states in a computation

## Pumping Lemma: Proof

• Let M be a machine that recognizes A

• Let p be the number of states of M

• Let s A and |s| ≥ p

• Then, there is a computation on M that accepts s,
• and this computation has length ≥ p+1 states

• Thus, this computation must repeat a state
• p states in the machine
• p+1 or more states in the computation
• pigeonhole principle (some state must be repeated in the computation)

• A repeated state defines a path that can be pumped
• Figure 1.72

## Using the Pumping Lemma to show a language is Non-Regular

• Assume language L is regular (then find a contradiction)

• If L is regular, then the pumping conditions hold for EVERY string in L that is long enough

• Show that the language is NOT regular by finding SOME STRING, call it s, that is long enough but for which the conditions don't hold

• To do this, you must show that it is IMPOSSIBLE to divide s into pieces (ie s = xyz) that meet the pumping conditions (usually condition 1)
• Usually you assume that 2 and perhaps 3 hold
• And then show that 1 can't also hold

• If you can find a string that is impossible to divide this way, then the language cannot be regular!

• Remember, you only need to find one string that cannot be pumped!

## Pumping Lemma Examples

• B = {0n1n | n ≥ 0}

• C = {w | w has an equal number of 0s and 1s}

• F = {ww | w ∈ {0,1}*}

• Example 1.76: D = 1n2 , n ≥ 0

• Example 1.77: E = {0i1j | i > j}

• E2 = {0i1j | i < j}

• L6 = {w | number of 0's in w < number of 1's in w}

• L7 = {(01)n0k | n > k ≥ 0}

## Pumping Lemma Example: 0 n1 n

• B = {0n1n}
• Assume B is regular, with pumping length p
• Let s be 0p1p
• s cannot be divided into xyz because
1. if y is all 0's then xyyz
2. if y is all 1's ...
3. if y is 0 k1k then xyyz may have equal number of 0's and 1's, but they will be in the wrong order
• Note that you can also use condition 3 to simplify the proof

## The Pumping Lemma Game

• Some people find it helpful to think of PL proofs as a competition

• Assume that you are in a competition
• You are trying to prove that language L is NOT regular.
• Your opponent is trying to prove that L IS regular

• The competition goes through the following steps:
1. Your opponent gives you p

2. You choose string s L with | s| ≥ p

3. Your opponent divides s into substrings xyz, with | y| > 0, and | xy| ≤ p

4. You pick an i such that xyiz is NOT in L

• You win (ie prove the language is not regular) if you can accomplish step 4

## Pumping Lemma Example 2: equal number of 0's and 1's

• C = { w | w has an equal number of 0's and 1's}
• Assume C is regular, with pumping length p
• Let s = 0p1p
• Note that s can be pumped if x and z are empty, but ...
• Condition 3 tells us that y must be all 0's
• in which case xyyz is not in C

• Could we have chosen s = (01)p

• Alternate proof:
• Regular languages are closed under intersection
• How did we prove this?
• C ∩ 0*1* = B
• B is not regular
• Thus, C is not regular

## Pumping Lemma Example 3: ww

• F = { ww | w ∈ {0,1}*}
• Let s be 0p10p1
• If x and z were empty, then we could pump, but ...
• Condition 3 tells us that y must be all 0's
• Thus, xyyz is not in F
• Notice the importance of choosing the correct string

## Pumping Lemma Example 4: 1n for square n

• D = { w | w = 1 n, n is a perfect square}
• Choose s = 1p*p

• y = 1 k with 1 ≤ kp
• Thus, xz = 1p*p-k

• But since $1 \le k\le p$,
• we have $k\lt 2p+1$
• and $p\times p-k=p^2-k\gt p^2-(2p+1) = p^2-2p-1=(p-1)^2$.
• Thus, $p^2-k$ is NOT a perfect square and
• therefore, $xz \not\in D$.
• Thus, $D$ is NOT regular.

## Pumping Lemma Example 5: 0i1j with i > j

• E = {0i1j | i > j}
• Let s = 0p+11p
• What has to be true of y
• Is xyyz in E?
• Is xz in E?
• Thus, $s$ cannot be pumped and $E$ is NOT regular

## Pumping Lemma Example 5a: 0i1j with i < j

• E = {0i1j | i < j}
• Let s be 0p1p+1
• What string is in $E$?
• What string is NOT in $E$?

## Pumping Lemma Example 6: number of 0's < number of 1's

• L6 = {w | number of 0's in w < number of 1's in w}
• What to choose for s

## Pumping Lemma Example 7: (01)n0k, n>k

• L7 = {(01)n0k | n > k ≥ 0}
• What to choose for s

• Note that we need to look at every way of dividing w

## Pumping Lemma Logic

• The theorem says that in a regular language, every string (that's long enough) has at least one way of being divided so that when pumped, the resulting strings are in that language.

• Thus, when proving that a string is not regular, you must show that
• there is at least one string (only one is needed) that has no way of being divided so that its pumped strings are in the language

• Here is the same argument in more formal terms:
• Theorem 1.70 states that if L is regular then for every s such that |s| ≥ p then there exists xyz such that s=xyz, y ≠ ε, |xy| ≤ p, and for which xyiz is in L for every i

• Thus, to prove that L is not regular you need to: prove that there is one string s longer than p such that for every xyz such that s=xyz, y ≠ ε and |xy| ≤ p, then there is an i for which xyiz is not in L.

• In 0n1n, we know that every way of dividing s has y being all 0's and so there is no reason to consider different ways of dividing s. But this is not always the case; sometimes you have to consider different ways of dividing s, as seen in Example 7.

## Pumping Lemma Logic Summary

• L Regular ⇒ long enough strings in L are pumpable

• a long enough string exists that is NOT pumpable ⇒ L NOT Regular

• Is this correct: every long string in L is pumpable ⇒ L Regular
• No: some non-regular languages have pumpable strings
• See example below

## A Language with Pumpable Strings that is NOT Regular

• Consider this language: G = { wwRv | v, w ∈ {0,1}+}

• We can pump any string:
• Let x = ???
• Let y = ???
• Why is xz in the language?
• Why is xyyz in the language?

• This language is not regular
• Intuition: no way to match w with wR
• Prove with the Myhill-Nerode Theorem
• Myhill-Nerode Theorem:
• Language A is Regular IFF the number of equivalence classes of RA is finite.
• We won't define the relation RA
• This is a necessary and sufficient condition for a language to be regular

• This language is Context Free

## Parting Thought

• Consider what we have shown:

• It is impossible to build a machine that will recognize a certain language

• And remember how we did it:

• Proof by contradiction

## Parting Thought Two

• Sometimes we prove that a language is not regular by showing that it's complement is not regular

• The complement of language L is the set of strings from Σ* that are not in L.

• It is easy to prove that the complement of a regular language is regular.

• We can also use closure of union and intersection to show complement.

ITEC 420 Course Page,