ITEC 420 - Chapter 1 - Regular Languages: Non-Regular Languages

Part 1: Automata and Languages

Chapter 1: Regular Languages

ITEC 420 - Section 1.4 - Non-Regular Languages

Regular Expressions

Consider these languages over Σ = {0, 1}

B = {0ⁿ1ⁿ | 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 s ∈ A and |s| ≥ p), then

Pumping Lemma for Regular Languages: In Different Words

If A is a regular language, then
- ∃ p ∈ Integers such that ∀s ∈ A with |s| ≥ 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

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

for each i ≥ 0, xyⁱz ∈ A: pumping the loop produces strings that are in the language

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

|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 = {0ⁿ1ⁿ | n ≥ 0}

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

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

Example 1.76: D = 1^n² , n ≥ 0

Example 1.77: E = {0ⁱ1^j | i > j}

E2 = {0ⁱ1^j | i < j}

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

L7 = {(01)ⁿ0^k | n > k ≥ 0}

Pumping Lemma Example: 0ⁿ1ⁿ

B = {0ⁿ1ⁿ}
Assume B is regular, with pumping length p
Let s be 0^p1^p
s cannot be divided into xyz because

if y is all 0's then xyyz
if y is all 1's ...
if y is 0^k1^k 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:

Your opponent gives you p

You choose string s∈ L with | s| ≥ p

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

You pick an i such that xyⁱz 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 = 0^p1^p

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 0^p10^p1
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: 1ⁿ for square n

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

y = 1 ^k with 1 ≤ k ≤ p
Thus, xz = 1^p*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: 0ⁱ1^j with i > j

E = {0ⁱ1^j | i > j}
Let s = 0^p+11^p
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: 0ⁱ1^j with i < j

E = {0ⁱ1^j | i < j}
Let s be 0^p1^p+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)ⁿ0^k, n>k

L7 = {(01)ⁿ0^k | 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 xyⁱz 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 xyⁱz is not in L.

In 0ⁿ1ⁿ, 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 = { ww^Rv | 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 w^R
Prove with the Myhill-Nerode Theorem
Myhill-Nerode Theorem:
- Language A is Regular IFF the number of equivalence classes of R_A is finite.
- We won't define the relation R_A
- 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,
Last modified on