The Pumping Lemma to Prove Irregularity
Pumping Lemma
Examples
L
>
= {ai
b
j
: i > j}
L
>
is not regular.
We prove it using the Pumping Lemma.
L
>
= {ai
b
j
: i > j}
L
>
is not regular.
•
Fix an arbitrary pumping length n>0.
L
>
= {ai
b
j
: i > j}
L
>
is not regular.
•
Fix an arbitrary pumping length n>0.
•
Choose a
proper
string s in L
>
.
L
>
= {ai
b
j
: i > j}
L
>
is not regular.
•
Fix an arbitrary pumping length n>0.
•
Choose a
proper
string s in L
>
.
|s|
≥ n
L
>
= {ai
b
j
: i > j}
L
>
is not regular.
•
Fix an arbitrary pumping length n>0.
•
Choose a
proper
string s in L
>
.
•
s = a
n+1
b
n
ϵ
L
>
.
aaa…aabb…b
n
n+1
L
>
= {ai
b
j
: i > j}
L
>
is not regular.
•
Fix an arbitrary pumping length n>0.
•
Choose a
proper
string s in L
>
.
•
s = a
n+1
b
n
ϵ
L
>
.
•
Consider all possible splittings of s in x,y,z with
the
desired properties
.
aaa…aabb…b
n
n+1
L
>
= {ai
b
j
: i > j}
L
>
is not regular.
•
Fix an arbitrary pumping length n>0.
•
Choose a
proper
string s in L
>
.
•
s = a
n+1
b
n
ϵ
L
>
.
•
Consider all possible splittings of s in x,y,z with
the
desired properties
.
|xy|≤ n
|y|
≥ 1
aaa…aabb…b
n
n+1
L
>
= {ai
b
j
: i > j}
L
>
is not regular.
•
Fix an arbitrary pumping length n>0.
•
Choose a
proper
string s in L
>
.
•
s = a
n+1
b
n
ϵ
L
>
.
•
Consider all possible splittings of s in x,y,z with
the
desired properties
.
|xy|≤ n
|y|
≥ 1
aaa…aabb…b
n
n+1
L
>
= {ai
b
j
: i > j}
L
>
is not regular.
•
Fix an arbitrary pumping length n>0.
•
Choose a
proper
string s in L
>
.
•
s = a
n+1
b
n
ϵ
L
>
.
•
Consider all possible splittings of s in x,y,z with
the
desired properties
.
|xy|≤ n
|y|
≥ 1
aaa…aabb…b
n
n+1
L
>
is not regular.
•
Fix an arbitrary pumping length n>0.
•
Choose a
proper
string s in L
>
.
•
s = a
n+1
b
n
ϵ
L
>
.
•
Consider all possible splittings of s in x,y,z with
the
desired properties
:
y = a
m
, 1
≤ m
≤ n.
aaa…aabb…b
L
>
= {ai
b
j
: i > j}
n
n+1
aaabb…b
n
n+1-m
L
>
is not regular.
•
Fix an arbitrary pumping length n>0.
•
Choose a
proper
string s in L
>
.
•
s = a
n+1
b
n
ϵ
L
>
.
•
Consider all possible splittings of s in x,y,z with
the
desired properties
:
y = a
m
, 1
≤ m
≤ n.
•
xz =a
n+1-m
b
n
∉
L
>
.
L
>
= {ai
b
j
: i > j}
n
L
>
= {ai
b
j
: i > j}
L
>
is not regular.
•
Fix an arbitrary pumping length n>0.
•
Choose a
proper
string s in L
>
.
•
s = a
n+1
b
n
ϵ
L
>
.
•
Consider all possible splittings of s in x,y,z with
the
desired properties
:
y = a
m
, 1
≤ m
≤ n.
•
xz =a
n+1-m
b
n
∉
L
>
.
•
So L
>
is not regular!
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
•
A string in the language?
•
First, figure out what this language is.
•
A string in the language? aabaab
L=
{ww : w in
{a,b
}
*
}
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
•
A string in the language? aabaab
•
Another string in the language?
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
•
A string in the language? aabaab
•
Another string in the language? aaaaaa
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
•
A string in the language? aabaab
•
Another string in the language? aaaaaa
•
A string not in the language?
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
•
A string in the language? aabaab
•
Another string in the language? aaaaaa
•
A string not in the language? abbb
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
•
A string in the language? aabaab
•
Another string in the language? aaaaaa
•
A string not in the language? abbb
•
Is
ε
in the language?
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
•
A string in the language? aabaab
•
Another string in the language? aaaaaa
•
A string not in the language? abbb
•
Is
ε
in the language? YES! (
ε = εε)
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
•
A string in the language? aabaab
•
Another string in the language? aaaaaa
•
A string not in the language? abbb
•
Is
ε
in the language? YES! (
ε = εε)
•
Is aa in the language?
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
•
A string in the language? aabaab
•
Another string in the language? aaaaaa
•
A string not in the language? abbb
•
Is
ε
in the language? YES! (
ε = εε)
•
Is aa in the language? YES!
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
•
A string in the language? aabaab
•
Another string in the language? aaaaaa
•
A string not in the language? abbb
•
Is
ε
in the language? YES! (
ε = εε)
•
Is aa in the language? YES!
•
Is a in the language?
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
•
A string in the language? aabaab
•
Another string in the language? aaaaaa
•
A string not in the language? abbb
•
Is
ε
in the language? YES! (
ε = εε)
•
Is aa in the language? YES!
•
Is a in the language? NO!
L=
{ww : w in
{a,b
}
*
}
•
First, figure out what this language is.
L = {ε,
aa, bb, aaaa, abab, baba, bbbb, aaaaaa …}
abaabba|abaabba
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
First fix an arbitrary number
n>0
to be the
pumping length.
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Choose wisely!!!
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = a
2n
aaa…aaa|aaa…aaa
n
n
aaa…aaa|aaa…aaa
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = a
2n
•
For x =
ε
,
y = a
2
, z = a
2n-2
z
y
n
n
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = a
2n
•
For x =
ε
,
y = a
2
, z = a
2n-2
aaaaa…aa|aaaa…aaa
z
y
n+1
n+1
y
ϵ
L
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = a
2n
•
For x =
ε
,
y = a
2
, z = a
2n-2
aaaaaaa…a|aaaaa…aaa
z
y
n+2
n+2
y
ϵ
L
y
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = a
2n
•
For x =
ε
,
y = a
2
, z = a
2n-2
a…aaaa|aa…aaa
z
n-1
n-1
ϵ
L
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = a
2n
•
For x =
ε
,
y = a
2
, z = a
2n-2
, there is no i: xy
i
z
∉
L!
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = a
2n
•
For x =
ε
,
y = a
2
, z = a
2n-2
, there is no i: xy
i
z
∉
L!
•
s = a
2n
doesn’t work!!!
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = (ab)
2n
abab…abab|abab…abab
n
n
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = (ab)
2n
•
For x =
ε
,
y = abab, z = (ab)
2n-2
abab…abab|abab…abab
n
n
z
y
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = (ab)
2n
•
For x =
ε
,
y = abab, z = (ab)
2n-2
abababab…ab|ababab…abab
n+1
n+1
y
z
y
ϵ
L
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = (ab)
2n
•
For x =
ε
,
y = abab, z = (ab)
2n-2
•
For any i, xy
i
z = (ab)
2i
(ab)
2n-2
= (ab)
2(i-n-2)
ϵ
L!
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
Example: For s = (ab)
2n
•
For x =
ε
,
y = abab, z = (ab)
2n-2
•
For any i, xy
i
z = (ab)
2i
(ab)
2n-2
= (ab)
2(i-n-2)
ϵ
L!
•
s = (ab)
2n
doesn’t work!
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
•
Use s = a
n
ba
n
b
aaaa…aab|aaaa...aab
n
n
aaaa…aab|aaaa...aab
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language.
•
Use s = a
n
ba
n
b
•
For any splitting of s in x,y,z with the
desired
properties
:
L=
{ww : w in
{a,b
}
*
}
n
n
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language
•
Use s = a
n
ba
n
b
•
For any splitting of s in x,y,z with the
desired
properties
: y = a
m
with 1
≤
m ≤ n.
L=
{ww : w in
{a,b
}
*
}
We prove that L is not regular by using the
pumping lemma.
•
Pumping length: n
•
Choose a
proper
string in the language
•
Use s = a
n
ba
n
b
•
For any splitting of s in x,y,z with the
desired
properties
: y = a
m
with 1
≤
m ≤ n.
•
Observe that xy
2
z = a
m+n
ba
n
b is not in L
QED
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
A first attempt to design a FA
q
10
q
11
q
12
q
13
q
2n
a,b
q
2n-1
q
2n-2
q
2n-3
q
1n
q
20
a,b
a,b
a,b
a,b
a,b
a,b
a,b
ε
...
...
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
A first attempt to design a FA
fails!
q
10
q
11
q
12
q
13
q
2n
a,b
q
2n-1
q
2n-2
q
2n-3
q
1n
q
20
a,b
a,b
a,b
a,b
a,b
a,b
a,b
ε
...
...
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Looks similar with L (L = {w1
w
2
: w
1
= w
2
}.
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Looks similar with L (L = {w1
w
2
: w
1
= w
2
}.
•
But the pumping lemma holds!
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Looks similar with L (L = {w1
w
2
: w
1
= w
2
}.
•
But the pumping lemma holds!
–
Fix pumping length k=2.
Is it regular?
•
Looks similar with L (L = {w1
w
2
: w
1
= w
2
}.
•
But the pumping lemma holds!
–
Fix pumping length k=2.
–
For every
proper
string s in L’,
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
abbba…abb|bbaba…aaa
n
n
2n
≥2
abbba…abb|bbaba…aaa
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Looks similar with L (L = {w1
w
2
: w
1
= w
2
}.
•
But the pumping lemma holds!
–
Fix pumping length k=2.
–
For every
proper
string s in L’,
–
split s in x, y, z with the
desired properties
.
z
y
n
n
|y|
≥1 and |xy|≤ 2
abbba…abb|bbaba…aaa
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Looks similar with L (L = {w1
w
2
: w
1
= w
2
}.
•
But the pumping lemma holds!
–
Fix pumping length k=2.
–
For every
proper
string s in L’,
–
split s in x =
ε
,y
=
first two symbols of s, z = rest.
z
y
n
n
ababbba…ab|bbbaba…aaa
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Looks similar with L (L = {w1
w
2
: w
1
= w
2
}.
•
But the pumping lemma holds!
–
Fix pumping length k=2.
–
For every
proper
string s in L’,
–
split s in x =
ε
,y
=
first two symbols of s, z = rest.
–
xy
2
z in L’.
n+1
ϵ
L’
z
y
y
n+1
abababbba…a|bbbbaba…aaa
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Looks similar with L (L = {w1
w
2
: w
1
= w
2
}.
•
But the pumping lemma holds!
–
Fix pumping length k=2.
–
For every
proper
string s in L’,
–
split s in x =
ε
,y
=
first two symbols of s, z = rest.
–
xy
3
z in L’.
n+2
ϵ
L’
z
y
y
y
n+2
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Looks similar with L (L = {w1
w
2
: w
1
= w
2
}.
•
But the pumping lemma holds!
–
Fix pumping length n=2.
–
For every
proper
string s in L’,
–
split s in x =
ε
,y
=
first two symbols of s, z = rest.
–
xy
0
z in L’.
bba…abbb|baba…aaa
ϵ
L’
z
n-1
n-1
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Looks similar with L (L = {w1
w
2
: w
1
= w
2
}.
•
But the pumping lemma holds!
–
Fix pumping length n=2.
–
For every
proper
string s in L’,
–
split s in x =
ε
,y
=
first two symbols of s, z = rest.
–
For every i
≥ 0
, xy
i
z in L’.
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Consider L’’ = {w : w has even length}.L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Consider L’’ = {w : w has even length}.Every string of even length
abbbaabb….…bbabaaaa
2n
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Consider L’’ = {w : w has even length}.Every string of even length
can be split into two parts of equal length
abbbaabb…
…bbabaaaa
n
|
n
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Consider L’’ = {w : w has even length}.Every string of even length
can be split into two parts of equal length
and vice versa.
abbbaabb….…bbabaaaa
2n
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Consider L’’ = {w : w has even length}.•
L’ = L’’
Every string of even length
can be split into two parts of equal length
and vice versa.
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
Consider L’’ = {w : w has even length}•
L’ = L’’
•
A DFA for L’’:
odd
a,b
even
a,b
L’ =
{w
1
w
2
: w
1
,w
2
ϵ
{a,b}*
,|w
1
|=|w
2
|
}
Is it regular?
•
YES!!!
•
L’ = L’’
•
A DFA for L’:
odd
a,b
a,b
even
Utilizing the Pumping Lemma to demonstrate the irregularity of languages where the condition L>= {aibj, i>j} is not satisfied. The process involves fixing a pumping length, choosing a suitable string from L, and exploring possible splittings of the string to show irregularity.
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
Pumping Lemma Examples
L>= {aibj: i > j} L>is not regular. We prove it using the Pumping Lemma.
L>= {aibj: i > j} L>is not regular. Fix an arbitrary pumping length n>0.
L>= {aibj: i > j} L>is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>.
L>= {aibj: i > j} L>is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. |s| n
L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. aaa aabb b n n+1
L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties. aaa aabb b n n+1
L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties. |xy| n |y| 1 aaa aabb b n n+1
L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties. |xy| n |y| 1 aaa aabb b n n+1
L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties. Y |xy| n |y| 1 aaa aabb b n+1 n
L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties: y = am, 1 m n. Y aaa aabb b n+1 n
L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties: y = am, 1 m n. xz =an+1-mbn L>. aaabb b n+1-m n n
L> = {aibj : i > j} L> is not regular. Fix an arbitrary pumping length n>0. Choose a proper string s in L>. s = an+1bn L>. Consider all possible splittings of s in x,y,z with the desired properties: y = am, 1 m n. xz =an+1-mbn L>. So L> is not regular!
L={ww : w in {a,b}*} First, figure out what this language is.
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language?
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language?
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language?
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language?
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language? YES! ( = )
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language? YES! ( = ) Is aa in the language?
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language? YES! ( = ) Is aa in the language? YES!
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language? YES! ( = ) Is aa in the language? YES! Is a in the language?
L={ww : w in {a,b}*} First, figure out what this language is. A string in the language? aabaab Another string in the language? aaaaaa A string not in the language? abbb Is in the language? YES! ( = ) Is aa in the language? YES! Is a in the language? NO!
L={ww : w in {a,b}*} First, figure out what this language is. L = { , aa, bb, aaaa, abab, baba, bbbb, aaaaaa } abaabba|abaabba
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma.
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. First fix an arbitrary number n>0 to be the pumping length.
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Choose wisely!!!
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n aaa aaa|aaa aaa n n
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2 z y aaa aaa|aaa aaa n n
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2 y y z aaaaa aa|aaaa aaa n+1 L n+1
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2 y y y z aaaaaaa a|aaaaa aaa n+2 L n+2
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2 z a aaaa|aa aaa n-1 L n-1
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2, there is no i: xyiz L!
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = a2n For x = , y = a2, z = a2n-2, there is no i: xyiz L! s = a2ndoesn t work!!!
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = (ab)2n abab abab|abab abab n n
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = (ab)2n For x = , y = abab, z = (ab)2n-2 y z abab abab|abab abab n n
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = (ab)2n For x = , y = abab, z = (ab)2n-2 y y z abababab ab|ababab abab n+1 L n+1
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = (ab)2n For x = , y = abab, z = (ab)2n-2 For any i, xyiz = (ab)2i(ab)2n-2 = (ab)2(i-n-2) L!
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Example: For s = (ab)2n For x = , y = abab, z = (ab)2n-2 For any i, xyiz = (ab)2i(ab)2n-2 = (ab)2(i-n-2) L! s = (ab)2ndoesn t work!
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Use s = anbanb aaaa aab|aaaa...aab n n
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language. Use s = anbanb For any splitting of s in x,y,z with the desired properties: aaaa aab|aaaa...aab n n
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language Use s = anbanb For any splitting of s in x,y,z with the desired properties: y = amwith 1 m n.
L={ww : w in {a,b}*} We prove that L is not regular by using the pumping lemma. Pumping length: n Choose a proper string in the language Use s = anbanb For any splitting of s in x,y,z with the desired properties: y = amwith 1 m n. Observe that xy2z = am+nbanb is not in L QED
L = {w1w2 : w1,w2 {a,b}*,|w1|=|w2|} Is it regular?
L = {w1w2 : w1,w2 {a,b}*,|w1|=|w2|} Is it regular? A first attempt to design a FA a,b a,b a,b a,b ... q10 q11 q12 q13 q1n a,b a,b a,b a,b ... q2n-1 q2n-2 q2n-3 q2n q20
L = {w1w2 : w1,w2 {a,b}*,|w1|=|w2|} Is it regular? A first attempt to design a FA fails! a,b a,b a,b a,b ... q10 q11 q12 q13 q1n a,b a,b a,b a,b ... q2n-1 q2n-2 q2n-3 q2n q20
