Non-Regular Languages and the Pumping Lemma
Non-regular languages - The
pumping lemma
Regular Languages
•
Regular languages are the languages which
are accepted by a Finite Automaton.
•
Not all languages are regular
Non-Regular Languages
•
L
0
= {ak
b
k
: k≤0} =
{ε}is a regular language
q
0a
q
0b
ε
Non-Regular Languages
•
L
1
= {ak
b
k
: k≤1} = {ε,
ab}
is regular
q
0a
q
1a
q
1b
q
0b
a
b
ε
ε
Non-Regular Languages
•
L
2
= {ak
b
k
: k≤2}
= {ε, ab, aabb} is regular
q
0a
q
1a
q
2a
q
2b
q
1b
q
0b
a
a
b
b
ε
ε
ε
Non-Regular Languages
•
L
3
= {ak
b
k
: k≤3} is regular
q
0a
q
1a
q
2a
q
3b
q
2b
q
1b
q
3a
q
0b
a
a
a
b
b
b
ε
ε
ε
ε
Non-Regular Languages
•
∀
n≥
0
,
L
n
= {ak
b
k
: k
≤
n} is regular
q
0a
q
1a
q
2a
q
nb
q
3a
q
na
q
0b
a
a
a
a
b
b
b
b
ε
q
(n-1)b
q
(n-2)b
q
(n-3)b
ε
ε
ε
ε
Non-Regular Languages
•
However L = {an
b
n
: n≥
0
} = U
n
≥
0
L
n
doesn’t
seem to be a regular language at all!
•
We need an infinite number of states to build
this automaton!
q
0a
q
1a
q
2a
q
nb
q
3a
a
a
a
a
b
b
b
b
q
(n-1)b
q
(n-2)b
q
(n-3)b
ε
ε
ε
ε
Non-Regular Languages
•
However L = {an
b
n
: n≥
0
} = U
n
≥
0
L
n
doesn’t
seem to be a regular language at all!
•
We need an infinite number of states to build
this automaton!
•
(Observe that you cannot use the fact that
regular languages are closed under union
because we have an infinite union)
Is this a proof?
NO!
In fact consider:
L’ = {s : s contains equal number of a and b}L’’ = {s : s contains equal number of ab and ba}L’ is indeed not regular but L’’ is regular!
WE NEED A MATHEMATICAL PROOF!!!
A proof that there is no FA that accepts L or L’.
Pigeonhole Principle
•
If we have n holes and m pigeons (m>n) then
there is a hole with at least two pigeons.
Pigeonhole Principle
•
If we have n holes and m pigeons (m>n) then
there is a hole with at least two pigeons.
PP and Finite Automata
•
If an automaton with n states accepts a string
with length m (m≥n) then for every accepting
path there should be at least one repeating
state.
s = aaba
PP and Finite Automata
•
If an automaton with n states accepts a string
with length m (m≥n) then for every accepting
path there should be at least one repeating
state.
s = aaba
a
a
a
b
PP and Finite Automata
•
If an automaton with n states accepts a string
with length m (m≥n) then for every accepting
path there should be at least one repeating
state.
Any string of the form aab*a should be accepted!
a
a
a
b
PP and FA continued
PP and FA continued
x
z
y
PP and FA continued
x
z
y
xyz
is accepted
PP and FA continued
x
z
y
xyyz
is accepted
PP and FA continued
x
z
y
xyyyz
is accepted
PP and FA continued
x
z
y
xz
is accepted
PP and FA continued
x
z
y
xy
i
z, for i ≥ 0
is accepted
The pumping lemma
For every
infinite
regular
language L
there exists a pumping length
n > 0
such that
for any string s in L with length
|s| ≥ n
we can write
s = xyz
with
|xy| ≤ n
and
|y|
≥ 1
such that
xy
i
z in L
for every
i
≥
0
.
Proof
•
If L is regular then there exists a DFA M which
accepts L. Set n to be M’s number of states.
•
L is infinite, there exists a string s with length
greater than n.
•
The number of states is n, the accepting path
for s is of length at most n.
•
The string is of length at least n, there is a part
in the path that is repeated.
Proof
•
Split s into 3 parts x, y, z with y being the first
repeated part.
•
Since we have n states the first repetition
should take place (|y|
≥ 1)
in at most n
transitions (|xy| ≤ n).
•
Since the path under y is a loop we can follow
it as many times as we want (maybe none).
•
Thus xy
i
z for any i ≥ 0 should lead us to the
same accepting state as xyz.
Prove that L is not regular
•
Given is an infinite language L.
Prove that L is not regular
•
Given is an infinite language L.
(
What if L is finite?
)
Prove that L is not regular
•
Given is an infinite language L
•
If L is regular
Prove that L is not regular
•
Given is an infinite language L
•
If L is regular
•
Pumping lemma holds:
–
There exists
a pumping length n such that
–
for all
proper
strings s in L
–
there is
a splitting of s in x,y,z (with the
desired
properties
) such that
–
for all
i xy
i
z is in L.
Prove that L is not regular
•
Given is an infinite language L
•
If L is regular
•
Pumping lemma holds:
–
There exists
a pumping length n such that
–
for all
proper
strings s in L
–
there is
a splitting of s in x,y,z (with the
desired
properties
) such that
–
for all
i xy
i
z is in L.
|y| ≥ 1 and |xy| ≤ n
|s| ≥ n
Prove that L is not regular
•
Given is an infinite language L
•
If L is regular the pumping lemma holds.
•
The negation of the pumping lemma:
–
For all
pumping lengths n
–
there exists
a
proper
string s in L such that
–
for every possible
splitting of s in x,y,z (with the
desired properties
)
–
there is
an i for which xy
i
z is
not
in L.
Prove that L is not regular
•
Given is an infinite language L
•
Assume L is regular (pumping lemma holds)
•
Prove the negation of the pumping lemma:
–
Fix
an
arbitrary
pumping length n.
–
Specify
a
proper
string s in L.
–
Show that
for every possible
splitting of s in x,y,z
(with the
desired properties
),
–
there is
an i for which xy
i
z is
not
in L.
Prove that L is not regular
•
Given is an infinite language L
•
Assume L is regular (pumping lemma holds)
•
Prove the negation of the pumping lemma:
–
Fix
an
arbitrary
pumping length n.
–
Specify
a
proper
string s in L.
–
Show that
for every possible
splitting of s in x,y,z
(with the
desired properties
),
–
there is
an i for which xy
i
z is
not
in L.
•
Contradiction!!!
Prove that L is not regular
•
Given is an infinite language L
•
Assume L is regular (pumping lemma holds)
•
Prove the negation of the pumping lemma:
–
Fix
an
arbitrary
pumping length n.
–
Specify
a
proper
string s in L.
–
Show that
for every possible
splitting of s in x,y,z
(with the
desired properties
),
–
there is
an i for which xy
i
z is
not
in L.
•
Contradiction!!!
L is not regular
Example
•
L = {an
b
n
: n ≥ 0} is not regular.
Proof:
Assume that L is regular. The pumping lemma
holds!
Example
•
L = {an
b
n
: n ≥ 0} is not regular.
Proof:
Fix an arbitrary pumping length
k
for L.
Example
•
L = {an
b
n
: n ≥ 0} is not regular.
Proof:
The string s = a
k
b
k
should be in the language.
Example
•
L = {an
b
n
: n ≥ 0} is not regular.
Proof:
s is
proper
: |s| = 2
k
is greater than
k
Example
•
L = {an
b
n
: n ≥ 0} is not regular.
Proof:
Consider all possible splittings of a
k
b
k
in the
form xyz with the
desired properties
:
•
|xy| ≤ k and
•
|y| ≥ 1
•
L = {an
b
n
: n ≥ 0} is not regular.
Proof:
Consider all possible splittings of a
k
b
k
in the
form xyz with the
desired properties
:
•
|xy| ≤ k and
•
|y| ≥ 1
Example
a a a a a a a a a b b b b b b b b b
k
k
•
L = {an
b
n
: n ≥ 0} is not regular.
Proof:
Consider all possible splittings of a
k
b
k
in the
form xyz with the
desired properties
:
•
|xy| ≤ k and
•
|y| ≥ 1
a a a a a a a a a b b b b b b b b b
Example
x
y
z
k
k
•
L = {an
b
n
: n ≥ 0} is not regular.
Proof:
Consider all possible splittings of a
k
b
k
in the
form xyz with the
desired properties
•
y = a
m
, for 1 ≤ m ≤ k
a a a a a a a a a b b b b b b b b b
Example
x
y
z
k
k
•
L = {an
b
n
: n ≥ 0} is not regular.
Proof:
Consider all possible splittings of a
k
b
k
in the
form xyz with the
desired properties
•
y = a
m
, for 1 ≤ m ≤ k
•
for i =2, xy
2
z = a
k+m
b
k
is not in L!
a a a a a a a a a a a a b b b b b b b b b
Example
x
y
z
y
•
L = {an
b
n
: n ≥ 0} is not regular.
Proof:
Consider all possible splittings of a
k
b
k
in the
form xyz with the
desired properties
•
xy
2
z is not in L!
CONTRADICTION!
a a a a a a a a a a a a b b b b b b b b b
Example
x
y
z
y
Try it yourself
•
Show that the following language is not a
regular language:
L
p
’ = {abj
c
j
| j ≥ 0}
•
Members: a, abc, abbcc, abbbccc, …
Try it yourself
•
Show that the following language is not a
regular language:
L
p
’ = {abj
c
j
| j ≥ 0}
•
Negation of the pumping lemma (
reminder
):
–
Fix
an
arbitrary
pumping length n.
–
Specify
a
proper
string s in L.
–
Show that
for every possible
splitting of s in x,y,z
(with the
desired properties
),
–
there is
an i for which xy
i
z is
not
in L.
How to use the pumping lemma
•
The pumping lemma mentions that if L is a
regular language then it can be pumped.
•
The contrapositive is true: If L cannot be
pumped then it shouldn’t be regular!
Show that L cannot be pumped to prove that L
is not regular.
How
not
to use the pumping lemma
•
The pumping lemma mentions that if L is a
regular language then it can be pumped.
•
The converse is not true: If a language can be
pumped this doesn’t mean that it is regular!
Do not try to show that L can be pumped in
order to prove that L is regular.
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
1.
L
p
is not regular.
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
1.
L
p
is not regular.
Proof:
•
L
p
’ = {abj
c
j
: j
≥0
} is not regular.
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
1.
L
p
is not regular.
Proof:
•
L
p
’ = {abj
c
j
: j
≥0
} is not regular.
•
L
p
’ = L
p
∩
L(ab*c*).
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
1.
L
p
is not regular.
Proof:
•
L
p
’ = {abj
c
j
: j
≥0
} is not regular.
•
L
p
’ = L
p
∩
L(ab*c*).
•
If L
p
was regular then L’ would be regular too.
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
2.
L
p
can be pumped
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
2.
L
p
can be pumped
Proof:
Prove that:
There is
a pumping length n such
that
for any
proper
s in L
p
there exists
a
splitting xyz of s with the
desired properties
such that
for all
i xy
i
z is in L
p
.
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
2.
L
p
can be pumped
Proof:
Choose pumping length n = 2
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
2.
L
p
can be pumped
Proof:
Choose pumping length n = 2
•
For i=0, j=0, k
≥2
: s = c
k
Set x=
ε,
y = c, z = c
k-1
For every i
≥0,
xy
i
z is in L
p
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
2.
L
p
can be pumped
Proof:
Choose pumping length n = 2
•
For i=0, j≥1, k
≥0
: s = b
j
c
k
Set x=
ε,
y = b, z = b
j-1
c
k
For every i≥0, xy
i
z is in L
p
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
2.
L
p
can be pumped
Proof:
Choose pumping length n = 2
•
For i=1 and any j ≥ 1: s = ab
j
c
j
Set x=
ε,
y = a, z = b
j
c
j
For every i≥0, xy
i
z is in L
p
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
2.
L
p
can be pumped
Proof:
Choose pumping length n = 2
•
For i=2 and any j, k ≥ 0: s = aab
j
c
k
Set x=
ε,
y = aa, z = b
j
c
k
For every i≥0, xy
i
z is in L
p
Pumping Lemma - Converse
•
For example consider the language
L
p
= {ai
b
j
c
k
: i,j,k
≥0
,
if i=1 then j=k}.
2.
L
p
can be pumped
Proof:
Choose pumping length n = 2
•
For i
≥3
and any j, k ≥ 0: s = aaa
i-2
b
j
c
k
Set x=
ε,
y = a, z aa
i-2
b
j
c
k
For every i≥0, xy
i
z is in L
p
The Universe
Regular languages
•
L = {an
b
n
: n ≥ 0}
•
L(ab*c*)
•
L
1000
={an
b
n
: n ≤ 1000}
Set of Languages over
Σ = {a, b, c}
Non-Regular
•
L
p
’
•
L
p
Dive into the world of regular and non-regular languages, exploring the concept of the pumping lemma. Learn about different types of non-regular languages and why some languages require an infinite number of states to be represented by a finite automaton. Find out why mathematical proofs are essential in determining the regularity of languages.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Non-regular languages - The pumping lemma
Regular Languages Regular languages are the languages which are accepted by a Finite Automaton. Not all languages are regular
Non-Regular Languages L0= {akbk: k 0} = { } is a regular language q0a q0b
Non-Regular Languages L1 = {akbk: k 1} = { , ab} is regular a q0a q1a b q1b q0b
Non-Regular Languages L2 = {akbk: k 2} = { , ab, aabb} is regular a a q0a q1a q2a b b q2b q1b q0b
Non-Regular Languages L3 = {akbk: k 3} is regular a a a q0a q1a q2a q3a b b b q3b q2b q1b q0b
Non-Regular Languages n 0,Ln = {akbk : k n} is regular a a a a q0a q1a q2a q3a qna b b b b q(n-3)b q(n-1)b q(n-2)b qnb q0b
Non-Regular Languages However L = {anbn: n 0} = Un 0 Lndoesn t seem to be a regular language at all! We need an infinite number of states to build this automaton! a a a a q0a q1a q2a q3a b b b b q(n-3)b q(n-1)b q(n-2)b qnb
Non-Regular Languages However L = {anbn: n 0} = Un 0 Lndoesn t seem to be a regular language at all! We need an infinite number of states to build this automaton! (Observe that you cannot use the fact that regular languages are closed under union because we have an infinite union)
Is this a proof? NO!In fact consider: L = {s : s contains equal number of a and b} L = {s : s contains equal number of ab and ba} L is indeed not regular but L is regular! WE NEED A MATHEMATICAL PROOF!!! A proof that there is no FA that accepts L or L .
Pigeonhole Principle If we have n holes and m pigeons (m>n) then there is a hole with at least two pigeons.
Pigeonhole Principle If we have n holes and m pigeons (m>n) then there is a hole with at least two pigeons.
PP and Finite Automata If an automaton with n states accepts a string with length m (m n) then for every accepting path there should be at least one repeating state. s = aaba
PP and Finite Automata If an automaton with n states accepts a string with length m (m n) then for every accepting path there should be at least one repeating state. b a a a s = aaba
PP and Finite Automata If an automaton with n states accepts a string with length m (m n) then for every accepting path there should be at least one repeating state. b a a a Any string of the form aab*a should be accepted!
PP and FA continued x z y
PP and FA continued x z y xyz is accepted
PP and FA continued x z y xyyz is accepted
PP and FA continued x z y xyyyz is accepted
PP and FA continued x z y xz is accepted
PP and FA continued x z y xyiz, for i 0 is accepted
The pumping lemma For every infinite regular language L there exists a pumping length n > 0 such that for any string s in L with length |s| n we can write s = xyz with |xy| n and |y| 1 such that xyiz in L for every i 0.
Proof If L is regular then there exists a DFA M which accepts L. Set n to be M s number of states. L is infinite, there exists a string s with length greater than n. The number of states is n, the accepting path for s is of length at most n. The string is of length at least n, there is a part in the path that is repeated.
Proof Split s into 3 parts x, y, z with y being the first repeated part. Since we have n states the first repetition should take place (|y| 1) in at most n transitions (|xy| n). Since the path under y is a loop we can follow it as many times as we want (maybe none). Thus xyiz for any i 0 should lead us to the same accepting state as xyz.
Prove that L is not regular Given is an infinite language L.
Prove that L is not regular Given is an infinite language L. (What if L is finite?)
Prove that L is not regular Given is an infinite language L If L is regular
Prove that L is not regular Given is an infinite language L If L is regular Pumping lemma holds: There exists a pumping length n such that for all proper strings s in L there is a splitting of s in x,y,z (with the desired properties) such that for all i xyiz is in L.
Prove that L is not regular Given is an infinite language L If L is regular Pumping lemma holds: There exists a pumping length n such that for all proper strings s in L there is a splitting of s in x,y,z (with the desired properties) such that for all i xyiz is in L. |s| n |y| 1 and |xy| n
Prove that L is not regular Given is an infinite language L If L is regular the pumping lemma holds. The negation of the pumping lemma: For all pumping lengths n there exists a proper string s in L such that for every possible splitting of s in x,y,z (with the desired properties) there is an i for which xyiz is not in L.
Prove that L is not regular Given is an infinite language L Assume L is regular (pumping lemma holds) Prove the negation of the pumping lemma: Fix an arbitrary pumping length n. Specify a proper string s in L. Show that for every possible splitting of s in x,y,z (with the desired properties), there is an i for which xyiz is not in L.
Prove that L is not regular Given is an infinite language L Assume L is regular (pumping lemma holds) Prove the negation of the pumping lemma: Fix an arbitrary pumping length n. Specify a proper string s in L. Show that for every possible splitting of s in x,y,z (with the desired properties), there is an i for which xyiz is not in L. Contradiction!!!
Prove that L is not regular Given is an infinite language L Assume L is regular (pumping lemma holds) Prove the negation of the pumping lemma: Fix an arbitrary pumping length n. Specify a proper string s in L. Show that for every possible splitting of s in x,y,z (with the desired properties), there is an i for which xyiz is not in L. Contradiction!!! L is not regular
Example L = {anbn: n 0} is not regular. Proof: Assume that L is regular. The pumping lemma holds!
Example L = {anbn: n 0} is not regular. Proof: Fix an arbitrary pumping length k for L.
Example L = {anbn: n 0} is not regular. Proof: The string s = akbk should be in the language.
Example L = {anbn: n 0} is not regular. Proof: s is proper: |s| = 2k is greater than k
Example L = {anbn: n 0} is not regular. Proof: Consider all possible splittings of akbk in the form xyz with the desired properties: |xy| k and |y| 1
Example L = {anbn: n 0} is not regular. Proof: Consider all possible splittings of akbk in the form xyz with the desired properties: |xy| k and |y| 1 a a a a a a a a a b b b b b b b b b k k
Example L = {anbn: n 0} is not regular. Proof: Consider all possible splittings of akbk in the form xyz with the desired properties: |xy| k and |y| 1 a a a a a a a a a b b b b b b b b b x y k k z
Example L = {anbn: n 0} is not regular. Proof: Consider all possible splittings of akbk in the form xyz with the desired properties y = am, for 1 m k k k a a a a a a a a a b b b b b b b b b x y z
Example L = {anbn: n 0} is not regular. Proof: Consider all possible splittings of akbk in the form xyz with the desired properties y = am, for 1 m k for i =2, xy2z = ak+mbk is not in L! a a a a a a a a a a a a b b b b b b b b b x y y z
Example L = {anbn: n 0} is not regular. Proof: Consider all possible splittings of akbk in the form xyz with the desired properties xy2z is not in L! CONTRADICTION! a a a a a a a a a a a a b b b b b b b b b x y y z
Try it yourself Show that the following language is not a regular language: Lp = {abjcj | j 0} Members: a, abc, abbcc, abbbccc,
Try it yourself Show that the following language is not a regular language: Lp = {abjcj | j 0} Negation of the pumping lemma (reminder): Fix an arbitrary pumping length n. Specify a proper string s in L. Show that for every possible splitting of s in x,y,z (with the desired properties), there is an i for which xyiz is not in L.
How to use the pumping lemma The pumping lemma mentions that if L is a regular language then it can be pumped. The contrapositive is true: If L cannot be pumped then it shouldn t be regular! Show that L cannot be pumped to prove that L is not regular.
How not to use the pumping lemma The pumping lemma mentions that if L is a regular language then it can be pumped. The converse is not true: If a language can be pumped this doesn t mean that it is regular! Do not try to show that L can be pumped in order to prove that L is regular.
Pumping Lemma - Converse For example consider the language Lp = {aibjck : i,j,k 0, if i=1 then j=k}.
Pumping Lemma - Converse For example consider the language Lp = {aibjck : i,j,k 0, if i=1 then j=k}. 1. Lp is not regular.
