CS310 : Automata Theory 2020
Lecture 13: Properties of regular languages
Instructor: S. Akshay
IIT Bombay, India
10-02-2020
Recap
I Automata models: DFA, NFA,-NFA I Algebraic model: Regular expressions
I Regular languages: All these models accept the same class of languages.
I Conversions: from NFA to DFA (Subset construction),-NFA to DFA, Regular expressions to -NFA, DFA to regular expressions
I Applications: text search using automata, regular expressions in GREP, emacs, python etc.
I Properties of regular languages
I Closure - under union, intersection, complementation, reversal I Pumping lemma.
I Limitations of regular languages: Examples of non-regular languages and how to show non-regularity using pumping lemma.
Recap
I Automata models: DFA, NFA,-NFA I Algebraic model: Regular expressions
I Regular languages: All these models accept the same class of languages.
I Conversions: from NFA to DFA (Subset construction),-NFA to DFA, Regular expressions to -NFA, DFA to regular expressions
I Applications: text search using automata, regular expressions in GREP, emacs, python etc.
I Properties of regular languages
I Closure - under union, intersection, complementation, reversal I Pumping lemma.
I Limitations of regular languages: Examples of non-regular languages and how to show non-regularity using pumping lemma.
Recap
I Automata models: DFA, NFA,-NFA I Algebraic model: Regular expressions
I Regular languages: All these models accept the same class of languages.
I Conversions: from NFA to DFA (Subset construction),-NFA to DFA, Regular expressions to -NFA, DFA to regular expressions
I Applications: text search using automata, regular expressions in GREP, emacs, python etc.
I Properties of regular languages
I Closure - under union, intersection, complementation, reversal I Pumping lemma.
I Limitations of regular languages: Examples of non-regular languages and how to show non-regularity using pumping lemma.
Recap
I Automata models: DFA, NFA,-NFA I Algebraic model: Regular expressions
I Regular languages: All these models accept the same class of languages.
I Conversions: from NFA to DFA (Subset construction),-NFA to DFA, Regular expressions to -NFA, DFA to regular expressions
I Applications: text search using automata, regular expressions in GREP, emacs, python etc.
I Properties of regular languages
I Closure - under union, intersection, complementation, reversal I Pumping lemma.
I Limitations of regular languages: Examples of non-regular languages and how to show non-regularity using pumping lemma.
Pumping lemma
Theorem (Pumping lemma): Let L be a regular language. Then I there exists a constant n such that
I for every word w ∈Lsuch that|w| ≥n,
I we can breakw into three wordsw =xyz, such that 1. y 6=,
2. |xy| ≤n, and
3. for allk ≥0,xykz ∈L.
Contrapositive of Pumping lemma: If I for all n,
I there is a word w ∈Lsuch that |w| ≥n,
I for each breakup of w into three words w =xyz such that 1. y 6=and
2. |xy| ≤n,
there is a k ≥0 such thatxykz 6∈L,thenL is not regular.
Pumping lemma
Theorem (Pumping lemma): Let L be a regular language. Then I there exists a constant n such that
I for every word w ∈Lsuch that|w| ≥n,
I we can breakw into three wordsw =xyz, such that 1. y 6=,
2. |xy| ≤n, and
3. for allk ≥0,xykz ∈L.
Contrapositive of Pumping lemma: If I for all n,
I there is a word w ∈Lsuch that |w| ≥n,
I for each breakup of w into three words w =xyz such that 1. y 6=and
2. |xy| ≤n,
Proving a language non regular
Consider language L
I For eachn, wepropose a word w ∈L of length at leastn
I We define parameterized word x and non-empty word y such that I xyz =w for some z and
I the parameter space coversall x andy such that |xy| ≤n. I For each split x andy, we choose ak such that xykz 6∈L. We have proven thatLis not regular.
Proving a language non regular
Consider language L
I For eachn, wepropose a wordw ∈L of length at leastn
I We define parameterized word x and non-empty word y such that I xyz =w for some z and
I the parameter space coversall x andy such that |xy| ≤n. I For each split x andy, we choose ak such that xykz 6∈L. We have proven thatLis not regular.
Proving a language non regular
Consider language L
I For eachn, wepropose a wordw ∈L of length at leastn
I We define parameterized word x and non-empty word y such that I xyz =w for some z and
I the parameter space coversall x andy such that |xy| ≤n.
I For each split x andy, we choose ak such that xykz 6∈L. We have proven thatLis not regular.
Proving a language non regular
Consider language L
I For eachn, wepropose a wordw ∈L of length at leastn
I We define parameterized word x and non-empty word y such that I xyz =w for some z and
I the parameter space coversall x andy such that |xy| ≤n.
I For each split x andy, we choose ak such that xykz 6∈L.
We have proven thatLis not regular.
Proving a language non regular
Consider language L
I For eachn, wepropose a wordw ∈L of length at leastn
I We define parameterized word x and non-empty word y such that I xyz =w for some z and
I the parameter space coversall x andy such that |xy| ≤n.
I For each split x andy, we choose ak such that xykz 6∈L.
We have proven that Lis not regular.
Some more examples using pumping lemma-I
Consider Lprime ={1p|p is a prime number.}.
I For eachn, letw = 1p such thatp >n+ 2 I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0. w = 1i
|{z}x
1j
|{z}y
1p−j−i
| {z }
z
I So, for any k ≥0, we have|xykz|= (p−j) +kj. I Choose k =p−j. Therefore,|xykz|= (p−j)(1 +j). I Now (p−k)>1 and 1 +j >1, which impliesxykz 6∈Lprime.
Some more examples using pumping lemma-I
Consider Lprime ={1p|p is a prime number.}.
I For eachn, letw = 1p such thatp >n+ 2
I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0. w = 1i
|{z}x
1j
|{z}y
1p−j−i
| {z }
z
I So, for any k ≥0, we have|xykz|= (p−j) +kj. I Choose k =p−j. Therefore,|xykz|= (p−j)(1 +j). I Now (p−k)>1 and 1 +j >1, which impliesxykz 6∈Lprime.
Some more examples using pumping lemma-I
Consider Lprime ={1p|p is a prime number.}.
I For eachn, letw = 1p such thatp >n+ 2 I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0. w = 1i
|{z}x
1j
|{z}y
1p−j−i
| {z }
z
I So, for any k ≥0, we have|xykz|= (p−j) +kj. I Choose k =p−j. Therefore,|xykz|= (p−j)(1 +j). I Now (p−k)>1 and 1 +j >1, which impliesxykz 6∈Lprime.
Some more examples using pumping lemma-I
Consider Lprime ={1p|p is a prime number.}.
I For eachn, letw = 1p such thatp >n+ 2 I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0.
w = 1i
|{z}x
1j
|{z}y
1p−j−i
| {z }
z
I So, for any k ≥0, we have|xykz|= (p−j) +kj. I Choose k =p−j. Therefore,|xykz|= (p−j)(1 +j). I Now (p−k)>1 and 1 +j >1, which impliesxykz 6∈Lprime.
Some more examples using pumping lemma-I
Consider Lprime ={1p|p is a prime number.}.
I For eachn, letw = 1p such thatp >n+ 2 I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0.
w = 1i
|{z}x
1j
|{z}y
1p−j−i
| {z }
z
I So, for any k≥0, we have|xykz|= (p−j) +kj.
I Choose k =p−j. Therefore,|xykz|= (p−j)(1 +j). I Now (p−k)>1 and 1 +j >1, which impliesxykz 6∈Lprime.
Some more examples using pumping lemma-I
Consider Lprime ={1p|p is a prime number.}.
I For eachn, letw = 1p such thatp >n+ 2 I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0.
w = 1i
|{z}x
1j
|{z}y
1p−j−i
| {z }
z
I So, for any k≥0, we have|xykz|= (p−j) +kj. I Choose k =p−j. Therefore,|xykz|= (p−j)(1 +j).
I Now (p−k)>1 and 1 +j >1, which impliesxykz 6∈Lprime.
Some more examples using pumping lemma-I
Consider Lprime ={1p|p is a prime number.}.
I For eachn, letw = 1p such thatp >n+ 2 I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0.
w = 1i
|{z}x
1j
|{z}y
1p−j−i
| {z }
z
I So, for any k≥0, we have|xykz|= (p−j) +kj. I Choose k =p−j. Therefore,|xykz|= (p−j)(1 +j).
I Now (p−k)>1 and 1 +j >1, which impliesxykz 6∈Lprime.
Some more examples using pumping lemma-II
Exercise
Consider L={1m2|m≥0}.
I For eachn, letw = 1n2
I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0. w = 1i
|{z}x
1j
|{z}y
1n2−j−i
| {z }
z
I So, |xykz|= (n2−j) +kj.
I Let k = 2. Therefore,|xykz|=n2+j. I Since 0<j ≤n,n2 <n2+j <n2+ 2n+ 1.
Therefore, xy2z 6∈L.
Some more examples using pumping lemma-II
Exercise
Consider L={1m2|m≥0}.
I For eachn, letw = 1n2
I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0. w = 1i
|{z}x
1j
|{z}y
1n2−j−i
| {z }
z
I So, |xykz|= (n2−j) +kj.
I Let k = 2. Therefore,|xykz|=n2+j. I Since 0<j ≤n,n2 <n2+j <n2+ 2n+ 1.
Therefore, xy2z 6∈L.
Some more examples using pumping lemma-II
Exercise
Consider L={1m2|m≥0}.
I For eachn, letw = 1n2
I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0. w = 1i
|{z}x
1j
|{z}y
1n2−j−i
| {z }
z
I So, |xykz|= (n2−j) +kj.
I Let k = 2. Therefore,|xykz|=n2+j. I Since 0<j ≤n,n2 <n2+j <n2+ 2n+ 1.
Therefore, xy2z 6∈L.
Some more examples using pumping lemma-II
Exercise
Consider L={1m2|m≥0}.
I For eachn, letw = 1n2
I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0.
w = 1i
|{z}x
1j
|{z}y
1n2−j−i
| {z }
z
I So, |xykz|= (n2−j) +kj.
I Let k = 2. Therefore,|xykz|=n2+j. I Since 0<j ≤n,n2 <n2+j <n2+ 2n+ 1.
Therefore, xy2z 6∈L.
Some more examples using pumping lemma-II
Exercise
Consider L={1m2|m≥0}.
I For eachn, letw = 1n2
I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0.
w = 1i
|{z}x
1j
|{z}y
1n2−j−i
| {z }
z
I So,|xykz|= (n2−j) +kj.
I Let k = 2. Therefore,|xykz|=n2+j. I Since 0<j ≤n,n2 <n2+j <n2+ 2n+ 1.
Therefore, xy2z 6∈L.
Some more examples using pumping lemma-II
Exercise
Consider L={1m2|m≥0}.
I For eachn, letw = 1n2
I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0.
w = 1i
|{z}x
1j
|{z}y
1n2−j−i
| {z }
z
I So,|xykz|= (n2−j) +kj.
I Let k = 2. Therefore,|xykz|=n2+j.
I Since 0<j ≤n,n2 <n2+j <n2+ 2n+ 1. Therefore, xy2z 6∈L.
Some more examples using pumping lemma-II
Exercise
Consider L={1m2|m≥0}.
I For eachn, letw = 1n2
I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0.
w = 1i
|{z}x
1j
|{z}y
1n2−j−i
| {z }
z
I So,|xykz|= (n2−j) +kj.
I Let k = 2. Therefore,|xykz|=n2+j. I Since 0<j ≤n,n2<n2+j <n2+ 2n+ 1.
Therefore, xy2z 6∈L.
Some more examples using pumping lemma-II
Exercise
Consider L={1m2|m≥0}.
I For eachn, letw = 1n2
I The first n characters ofw are 1n.
I Let x= 1i andy = 1j, wherei+j ≤n andj 6= 0.
w = 1i
|{z}x
1j
|{z}y
1n2−j−i
| {z }
z
I So,|xykz|= (n2−j) +kj.
I Let k = 2. Therefore,|xykz|=n2+j. I Since 0<j ≤n,n2<n2+j <n2+ 2n+ 1.
Therefore, xy2z 6∈L.
Some more examples using pumping lemma-III
Example of pumping down!
Is this regular: L={0`1m|` >m}?
I For eachn, letw = 0n1n
I Any breakup ofw hasx= 0i andy = 0j, wherei+j ≤n andj 6= 0. w = 0i
|{z}x
0j
|{z}y
0n−j−i1n
| {z }
z
I if k >2, we getxykz = 0i0j+20n−j−i1n∈L, so NOT enough! I However, let k= 0 (pumping down). Then,xykz = 0i0n−j−i1n6∈L. I This completes the proof.
Some more examples using pumping lemma-III
Example of pumping down!
Is this regular: L={0`1m|` >m}?
I For eachn, letw = 0n1n
I Any breakup ofw hasx= 0i andy = 0j, wherei+j ≤n andj 6= 0. w = 0i
|{z}x
0j
|{z}y
0n−j−i1n
| {z }
z
I if k >2, we getxykz = 0i0j+20n−j−i1n∈L, so NOT enough! I However, let k= 0 (pumping down). Then,xykz = 0i0n−j−i1n6∈L. I This completes the proof.
Some more examples using pumping lemma-III
Example of pumping down!
Is this regular: L={0`1m|` >m}?
I For eachn, letw = 0n1n
I Any breakup ofw hasx= 0i andy = 0j, wherei+j ≤n andj 6= 0.
w = 0i
|{z}x
0j
|{z}y
0n−j−i1n
| {z }
z
I if k >2, we getxykz = 0i0j+20n−j−i1n∈L, so NOT enough! I However, let k= 0 (pumping down). Then,xykz = 0i0n−j−i1n6∈L. I This completes the proof.
Some more examples using pumping lemma-III
Example of pumping down!
Is this regular: L={0`1m|` >m}?
I For eachn, letw = 0n1n
I Any breakup ofw hasx= 0i andy = 0j, wherei+j ≤n andj 6= 0.
w = 0i
|{z}x
0j
|{z}y
0n−j−i1n
| {z }
z
I if k>2, we getxykz = 0i0j+20n−j−i1n ∈L, so NOT enough!
I However, let k= 0 (pumping down). Then,xykz = 0i0n−j−i1n6∈L. I This completes the proof.
Some more examples using pumping lemma-III
Example of pumping down!
Is this regular: L={0`1m|` >m}?
I For eachn, letw = 0n1n
I Any breakup ofw hasx= 0i andy = 0j, wherei+j ≤n andj 6= 0.
w = 0i
|{z}x
0j
|{z}y
0n−j−i1n
| {z }
z
I if k>2, we getxykz = 0i0j+20n−j−i1n ∈L, so NOT enough!
I However, letk = 0 (pumping down). Then,xykz = 0i0n−j−i1n6∈L.
I This completes the proof.
Some more examples using pumping lemma-III
Example of pumping down!
Is this regular: L={0`1m|` >m}?
I For eachn, letw = 0n1n
I Any breakup ofw hasx= 0i andy = 0j, wherei+j ≤n andj 6= 0.
w = 0i
|{z}x
0j
|{z}y
0n−j−i1n
| {z }
z
I if k>2, we getxykz = 0i0j+20n−j−i1n ∈L, so NOT enough!
I However, letk = 0 (pumping down). Then,xykz = 0i0n−j−i1n6∈L.
I This completes the proof.
Some more examples using pumping lemma-IV
Using regularity properties Is this regular: L={0`1m|`6=m}?
I SupposeL is regular. Note that Σ ={0,1}.
I Consider the language L0 =L∩0∗1∗, where Lis the complement of L. I This must be regular by closure properties.
I But L0 ={0n1n|n∈N}, which we know is not regular. I Hence we have a contradiction and Lis not regular.
Some more examples using pumping lemma-IV
Using regularity properties Is this regular: L={0`1m|`6=m}?
I SupposeL is regular. Note that Σ ={0,1}.
I Consider the language L0 =L∩0∗1∗, where Lis the complement of L. I This must be regular by closure properties.
I But L0 ={0n1n|n∈N}, which we know is not regular. I Hence we have a contradiction and Lis not regular.
Some more examples using pumping lemma-IV
Using regularity properties Is this regular: L={0`1m|`6=m}?
I SupposeL is regular. Note that Σ ={0,1}.
I Consider the language L0 =L∩0∗1∗, where Lis the complement of L.
I This must be regular by closure properties.
I But L0 ={0n1n|n∈N}, which we know is not regular. I Hence we have a contradiction and Lis not regular.
Some more examples using pumping lemma-IV
Using regularity properties Is this regular: L={0`1m|`6=m}?
I SupposeL is regular. Note that Σ ={0,1}.
I Consider the language L0 =L∩0∗1∗, where Lis the complement of L.
I This must be regular by closure properties.
I But L0 ={0n1n|n∈N}, which we know is not regular. I Hence we have a contradiction and Lis not regular.
Some more examples using pumping lemma-IV
Using regularity properties Is this regular: L={0`1m|`6=m}?
I SupposeL is regular. Note that Σ ={0,1}.
I Consider the language L0 =L∩0∗1∗, where Lis the complement of L.
I This must be regular by closure properties.
I But L0 ={0n1n|n∈N}, which we know is not regular.
I Hence we have a contradiction and Lis not regular.
Need for infinite memory
Feels like all non-regular languages needed to remember infinite memory.
In{0n1n|n≥0}we need to remember the numberof seen 0s and count the 1s to match.
Finite number of statescannot count unboundedlyincreasing number.
Need for infinite memory
Feels like all non-regular languages needed to remember infinite memory.
In {0n1n|n≥0}we need to remember the numberof seen 0s and count the 1s to match.
Finite number of statescannot count unboundedlyincreasing number.
Need for infinite memory
Feels like all non-regular languages needed to remember infinite memory.
In {0n1n|n≥0}we need to remember the numberof seen 0s and count the 1s to match.
Finite number of statescannot count unboundedlyincreasing number.
Converse does not hold!
Pumping lemma holds for the following non-regular language.
L={canbn|n≥0}
| {z }
L1
∪ {ckw|k 6= 1 andw ∈ {a,b}∗}
| {z }
L2
Applying contrapositive of pumping lemma: I For L1, the long enough word has to be can.
I But then, consider the partition of w =xyz wherex =,y =c I Then if you pump up , i.e., ckanbn∈L2 ⊆L
I And if you pump down, i.e., c0anbn=anbn∈L2 ⊆L I And of course, i.e.,c1anbn∈L1 ⊆L.
In other words,
I This language satisfies pumping lemma! I But it is non-regular(Show this!)
Converse does not hold!
Pumping lemma holds for the following non-regular language.
L={canbn|n≥0}
| {z }
L1
∪ {ckw|k 6= 1 andw ∈ {a,b}∗}
| {z }
L2
Applying contrapositive of pumping lemma:
I For L1, the long enough word has to be can.
I But then, consider the partition of w =xyz wherex =,y =c I Then if you pump up , i.e., ckanbn∈L2 ⊆L
I And if you pump down, i.e., c0anbn=anbn∈L2 ⊆L I And of course, i.e.,c1anbn∈L1 ⊆L.
In other words,
I This language satisfies pumping lemma! I But it is non-regular(Show this!)
Converse does not hold!
Pumping lemma holds for the following non-regular language.
L={canbn|n≥0}
| {z }
L1
∪ {ckw|k 6= 1 andw ∈ {a,b}∗}
| {z }
L2
Applying contrapositive of pumping lemma:
I For L1, the long enough word has to be can.
I But then, consider the partition of w =xyz wherex=,y =c
I Then if you pump up , i.e., ckanbn∈L2 ⊆L
I And if you pump down, i.e., c0anbn=anbn∈L2 ⊆L I And of course, i.e.,c1anbn∈L1 ⊆L.
In other words,
I This language satisfies pumping lemma! I But it is non-regular(Show this!)
Converse does not hold!
Pumping lemma holds for the following non-regular language.
L={canbn|n≥0}
| {z }
L1
∪ {ckw|k 6= 1 andw ∈ {a,b}∗}
| {z }
L2
Applying contrapositive of pumping lemma:
I For L1, the long enough word has to be can.
I But then, consider the partition of w =xyz wherex=,y =c I Then if you pump up , i.e., ckanbn∈L2 ⊆L
I And if you pump down, i.e., c0anbn=anbn∈L2 ⊆L I And of course, i.e.,c1anbn∈L1 ⊆L.
In other words,
I This language satisfies pumping lemma! I But it is non-regular(Show this!)
Converse does not hold!
Pumping lemma holds for the following non-regular language.
L={canbn|n≥0}
| {z }
L1
∪ {ckw|k 6= 1 andw ∈ {a,b}∗}
| {z }
L2
Applying contrapositive of pumping lemma:
I For L1, the long enough word has to be can.
I But then, consider the partition of w =xyz wherex=,y =c I Then if you pump up , i.e., ckanbn∈L2 ⊆L
I And if you pump down, i.e., c0anbn=anbn∈L2 ⊆L
I And of course, i.e.,c1anbn∈L1 ⊆L. In other words,
I This language satisfies pumping lemma! I But it is non-regular(Show this!)
Converse does not hold!
Pumping lemma holds for the following non-regular language.
L={canbn|n≥0}
| {z }
L1
∪ {ckw|k 6= 1 andw ∈ {a,b}∗}
| {z }
L2
Applying contrapositive of pumping lemma:
I For L1, the long enough word has to be can.
I But then, consider the partition of w =xyz wherex=,y =c I Then if you pump up , i.e., ckanbn∈L2 ⊆L
I And if you pump down, i.e., c0anbn=anbn∈L2 ⊆L I And of course, i.e.,c1anbn∈L1 ⊆L.
In other words,
I This language satisfies pumping lemma! I But it is non-regular(Show this!)
Converse does not hold!
Pumping lemma holds for the following non-regular language.
L={canbn|n≥0}
| {z }
L1
∪ {ckw|k 6= 1 andw ∈ {a,b}∗}
| {z }
L2
Applying contrapositive of pumping lemma:
I For L1, the long enough word has to be can.
I But then, consider the partition of w =xyz wherex=,y =c I Then if you pump up , i.e., ckanbn∈L2 ⊆L
I And if you pump down, i.e., c0anbn=anbn∈L2 ⊆L I And of course, i.e.,c1anbn∈L1 ⊆L.
In other words,
More generalized pumping lemma
We have been looking for evidence of bad pumping in prefixes of words.
We can look for such evidence for any subword of length greater thann.
Theorem
Lis not regular if, I for eachn,
I there are words u,w, andv such thatuwv ∈Land|w| ≥n
I for each breakup of w into three words xyz =w such that y 6=and
|xy| ≤n then
I there is a k ≥0 such thatuxykzv 6∈L.
I In our earlier version of pumping lemma, u=. I Can we use this version for the previous example? I Is this an iff condition?
More generalized pumping lemma
We have been looking for evidence of bad pumping in prefixes of words. We can look for such evidence for any subword of length greater than n.
Theorem
Lis not regular if, I for eachn,
I there are words u,w, andv such thatuwv ∈Land|w| ≥n
I for each breakup of w into three words xyz =w such that y 6=and
|xy| ≤n then
I there is a k ≥0 such thatuxykzv 6∈L.
I In our earlier version of pumping lemma, u=. I Can we use this version for the previous example? I Is this an iff condition?
More generalized pumping lemma
We have been looking for evidence of bad pumping in prefixes of words. We can look for such evidence for any subword of length greater than n.
Theorem
L is not regular if, I for eachn,
I there are words u,w, andv such thatuwv ∈Land|w| ≥n
I for each breakup of w into three words xyz =w such that y 6=and
|xy| ≤n then
I there is a k ≥0 such thatuxykzv 6∈L.
I In our earlier version of pumping lemma, u=. I Can we use this version for the previous example? I Is this an iff condition?
More generalized pumping lemma
We have been looking for evidence of bad pumping in prefixes of words. We can look for such evidence for any subword of length greater than n.
Theorem
L is not regular if, I for eachn,
I there are words u,w, andv such thatuwv ∈Land|w| ≥n
I for each breakup of w into three words xyz =w such that y 6=and
|xy| ≤n then
I there is a k ≥0 such thatuxykzv 6∈L.
I In our earlier version of pumping lemma, u=. I Can we use this version for the previous example? I Is this an iff condition?
More generalized pumping lemma
We have been looking for evidence of bad pumping in prefixes of words. We can look for such evidence for any subword of length greater than n.
Theorem
L is not regular if, I for eachn,
I there are words u,w, andv such thatuwv ∈Land|w| ≥n
I for each breakup of w into three words xyz =w such that y 6=and
|xy| ≤n then
I there is a k ≥0 such thatuxykzv 6∈L.
I In our earlier version of pumping lemma, u=. I Can we use this version for the previous example? I Is this an iff condition?
More generalized pumping lemma
We have been looking for evidence of bad pumping in prefixes of words. We can look for such evidence for any subword of length greater than n.
Theorem
L is not regular if, I for eachn,
I there are words u,w, andv such thatuwv ∈Land|w| ≥n
I for each breakup of w into three words xyz =w such that y 6=and
|xy| ≤n then
I there is a k ≥0 such thatuxykzv 6∈L.
I In our earlier version of pumping lemma, u=. I Can we use this version for the previous example? I Is this an iff condition?
More generalized pumping lemma
We have been looking for evidence of bad pumping in prefixes of words. We can look for such evidence for any subword of length greater than n.
Theorem
L is not regular if, I for eachn,
I there are words u,w, andv such thatuwv ∈Land|w| ≥n
I for each breakup of w into three words xyz =w such that y 6=and
|xy| ≤n then
I there is a k ≥0 such thatuxykzv 6∈L.
I In our earlier version of pumping lemma,u =.
I Can we use this version for the previous example? I Is this an iff condition?
More generalized pumping lemma
We have been looking for evidence of bad pumping in prefixes of words. We can look for such evidence for any subword of length greater than n.
Theorem
L is not regular if, I for eachn,
I there are words u,w, andv such thatuwv ∈Land|w| ≥n
I for each breakup of w into three words xyz =w such that y 6=and
|xy| ≤n then
I there is a k ≥0 such thatuxykzv 6∈L.
I In our earlier version of pumping lemma,u =. I Can we use this version for the previous example?
I Is this an iff condition?
More generalized pumping lemma
We have been looking for evidence of bad pumping in prefixes of words. We can look for such evidence for any subword of length greater than n.
Theorem
L is not regular if, I for eachn,
I there are words u,w, andv such thatuwv ∈Land|w| ≥n
I for each breakup of w into three words xyz =w such that y 6=and
|xy| ≤n then
I there is a k ≥0 such thatuxykzv 6∈L.
I In our earlier version of pumping lemma,u =. I Can we use this version for the previous example?
I Is this an iff condition?
Properties of regular languages
Let L be a regular language recognized by A= (Q,Σ, δ,q0,F) I For all x,y ∈Σ∗, we define
I x ≡Ay iff ˆδ(q0,x) = ˆδ(q0,y)
I That is, the state reached after x andy are the same. What are the properties of ≡A
I reflexive, symmetric and transitive. I It is an equivalence relation.
I What are other properties of this relation?
Properties of regular languages
Let L be a regular language recognized by A= (Q,Σ, δ,q0,F) I For all x,y ∈Σ∗, we define
I x ≡Ay iff ˆδ(q0,x) = ˆδ(q0,y)
I That is, the state reached after x andy are the same.
What are the properties of ≡A I reflexive, symmetric and transitive. I It is an equivalence relation.
I What are other properties of this relation?
Properties of regular languages
Let L be a regular language recognized by A= (Q,Σ, δ,q0,F) I For all x,y ∈Σ∗, we define
I x ≡Ay iff ˆδ(q0,x) = ˆδ(q0,y)
I That is, the state reached after x andy are the same.
What are the properties of ≡A
I reflexive, symmetric and transitive. I It is an equivalence relation.
I What are other properties of this relation?
Properties of regular languages
Let L be a regular language recognized by A= (Q,Σ, δ,q0,F) I For all x,y ∈Σ∗, we define
I x ≡Ay iff ˆδ(q0,x) = ˆδ(q0,y)
I That is, the state reached after x andy are the same.
What are the properties of ≡A I reflexive, symmetric and transitive.
I It is an equivalence relation.
I What are other properties of this relation?
Properties of regular languages
Let L be a regular language recognized by A= (Q,Σ, δ,q0,F) I For all x,y ∈Σ∗, we define
I x ≡Ay iff ˆδ(q0,x) = ˆδ(q0,y)
I That is, the state reached after x andy are the same.
What are the properties of ≡A I reflexive, symmetric and transitive.
I It is an equivalence relation.
I What are other properties of this relation?
Properties of regular languages
Let L be a regular language recognized by A= (Q,Σ, δ,q0,F) I For all x,y ∈Σ∗, we define
I x ≡Ay iff ˆδ(q0,x) = ˆδ(q0,y)
I That is, the state reached after x andy are the same.
What are the properties of ≡A I reflexive, symmetric and transitive.
I It is an equivalence relation.
I What are other properties of this relation?
Properties of ≡
AI For all x,y ∈Σ∗ anda∈Σ if x≡A y thenx·a≡A y·a (right congruence)
I if x≡A y then x ∈L(A) iff y ∈L(A) refinement
I The number of equivalence classes of ≡A is finite. Why? finite index Myhill Nerode relation
Equivalence relation on Σ∗ satisfying the above three properties. Theorem
For any regular language, there is a Myhill-Nerode relation What about the converse?
Properties of ≡
AI For all x,y ∈Σ∗ anda∈Σ if x≡A y thenx·a≡A y·a (right congruence)
I if x≡A y then x ∈L(A) iff y ∈L(A) refinement
I The number of equivalence classes of ≡A is finite. Why? finite index Myhill Nerode relation
Equivalence relation on Σ∗ satisfying the above three properties. Theorem
For any regular language, there is a Myhill-Nerode relation What about the converse?
Properties of ≡
AI For all x,y ∈Σ∗ anda∈Σ if x≡A y thenx·a≡A y·a (right congruence)
I if x≡A y then x ∈L(A) iff y ∈L(A) refinement
I The number of equivalence classes of ≡A is finite. Why? finite index Myhill Nerode relation
Equivalence relation on Σ∗ satisfying the above three properties. Theorem
For any regular language, there is a Myhill-Nerode relation What about the converse?
Properties of ≡
AI For all x,y ∈Σ∗ anda∈Σ if x≡A y thenx·a≡A y·a (right congruence)
I if x≡A y then x ∈L(A) iff y ∈L(A) refinement
I The number of equivalence classes of ≡A is finite. Why? finite index
Myhill Nerode relation
Equivalence relation on Σ∗ satisfying the above three properties. Theorem
For any regular language, there is a Myhill-Nerode relation What about the converse?
Properties of ≡
AI For all x,y ∈Σ∗ anda∈Σ if x≡A y thenx·a≡A y·a (right congruence)
I if x≡A y then x ∈L(A) iff y ∈L(A) refinement
I The number of equivalence classes of ≡A is finite. Why? finite index Myhill Nerode relation
Equivalence relation on Σ∗ satisfying the above three properties.
Theorem
For any regular language, there is a Myhill-Nerode relation What about the converse?
Properties of ≡
AI For all x,y ∈Σ∗ anda∈Σ if x≡A y thenx·a≡A y·a (right congruence)
I if x≡A y then x ∈L(A) iff y ∈L(A) refinement
I The number of equivalence classes of ≡A is finite. Why? finite index Myhill Nerode relation
Equivalence relation on Σ∗ satisfying the above three properties.
Theorem
For any regular language, there is a Myhill-Nerode relation
What about the converse?
Properties of ≡
AI For all x,y ∈Σ∗ anda∈Σ if x≡A y thenx·a≡A y·a (right congruence)
I if x≡A y then x ∈L(A) iff y ∈L(A) refinement
I The number of equivalence classes of ≡A is finite. Why? finite index Myhill Nerode relation
Equivalence relation on Σ∗ satisfying the above three properties.
Theorem
For any regular language, there is a Myhill-Nerode relation What about the converse?