Part 1: Automata and Languages
Chapter 1: Regular Languages
ITEC 420  Section 1.4  NonRegular Languages
Regular Expressions
 Consider these languages over Σ = {0, 1}

B = {0^{n}1^{n}  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
 s may be divided into three pieces, s = xyz, and
 s satisfies the following conditions:
 for each i ≥ 0, xy^{i}z ∈ A
 y > 0 (ie y ≠ ε)
 xy ≤ p
Pumping Lemma for Regular Languages: In Different Words
 If A is a regular language, then
 ∃ p ∈ Integers such that ∀s ∈
A with s ≥ p,
 ∃ x, y, z such that
 s = xyz
 xy^{i}z ∈ A, ∀i ≥ 0,
 y > 0
 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
 s can be divided in 3 substrings, x, y, z
 for each i ≥ 0, xy^{i}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
Using the Pumping Lemma to show a language is NonRegular
 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^{n}1^{n}  n ≥ 0}

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

F = {ww  w ∈ {0,1}^{*}}
 Example 1.76: D = 1^{n2} , n ≥ 0
 Example 1.77:
E = {0^{i}1^{j}  i >
j}

E2 = {0^{i}1^{j}  i <
j}
 L6 = {w  number of 0's in w < number of 1's in w}
 L7 = {(01)^{n}0^{k}  n > k ≥ 0}
Pumping Lemma Example:
0^{ n}1^{ n}
 B = {0^{n}1^{n}}
 Assume B is regular, with pumping length p
 Let s be 0^{p}1^{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^{ k}1^{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^{i}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^{p}1^{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
 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^{p}10^{p}1
 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^{n} for square n
 D = { w  w = 1^{ n}, n is a perfect
square}
 Choose s = 1^{p*p }
 y = 1 ^{k} with 1 ≤ k ≤ p
 Thus, xz = 1^{p*pk}
 But since $1 \le k\le p$,
 we have $k\lt 2p+1$
 and $p\times pk=p^2k\gt p^2(2p+1) = p^22p1=(p1)^2$.
 Thus, $p^2k$ is NOT a perfect square and
 therefore, $xz \not\in D$.
 Thus, $D$ is NOT regular.
Pumping Lemma Example 5:
0^{i}1^{j} with i > j
 E = {0^{i}1^{j}  i > j}
 Let s = 0^{p+1}1^{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^{i}1^{j} with i < j
 E = {0^{i}1^{j}  i < j}
 Let s be 0^{p}1^{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)^{n}0^{k}, n>k
 L7 = {(01)^{n}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^{i}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^{i}z is not in L.
 In 0^{n}1^{n},
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 nonregular languages have pumpable strings
 See example below
A Language with Pumpable Strings that is NOT Regular
 Consider this language: G = { ww^{R}v  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 MyhillNerode Theorem
 MyhillNerode 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:
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