## 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 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.

### 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,xy^{k}z ∈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 thatxy^{k}z 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,xy^{k}z ∈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 xy^{k}z 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 xy^{k}z 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 xy^{k}z 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 xy^{k}z 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 xy^{k}z 6∈L.

We have proven that Lis not regular.

### Some more examples using pumping lemma-I

Consider L_{prime} ={1^{p}|p is a prime number.}.

I For eachn, letw = 1^{p} such thatp >n+ 2
I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.
w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{p−j−i}

| {z }

z

I So, for any k ≥0, we have|xy^{k}z|= (p−j) +kj.
I Choose k =p−j. Therefore,|xy^{k}z|= (p−j)(1 +j).
I Now (p−k)>1 and 1 +j >1, which impliesxy^{k}z 6∈L_{prime}.

### Some more examples using pumping lemma-I

Consider L_{prime} ={1^{p}|p is a prime number.}.

I For eachn, letw = 1^{p} such thatp >n+ 2

I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.
w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{p−j−i}

| {z }

z

I So, for any k ≥0, we have|xy^{k}z|= (p−j) +kj.
I Choose k =p−j. Therefore,|xy^{k}z|= (p−j)(1 +j).
I Now (p−k)>1 and 1 +j >1, which impliesxy^{k}z 6∈L_{prime}.

### Some more examples using pumping lemma-I

Consider L_{prime} ={1^{p}|p is a prime number.}.

I For eachn, letw = 1^{p} such thatp >n+ 2
I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.
w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{p−j−i}

| {z }

z

I So, for any k ≥0, we have|xy^{k}z|= (p−j) +kj.
I Choose k =p−j. Therefore,|xy^{k}z|= (p−j)(1 +j).
I Now (p−k)>1 and 1 +j >1, which impliesxy^{k}z 6∈L_{prime}.

### Some more examples using pumping lemma-I

Consider L_{prime} ={1^{p}|p is a prime number.}.

I For eachn, letw = 1^{p} such thatp >n+ 2
I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.

w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{p−j−i}

| {z }

z

^{k}z|= (p−j) +kj.
I Choose k =p−j. Therefore,|xy^{k}z|= (p−j)(1 +j).
I Now (p−k)>1 and 1 +j >1, which impliesxy^{k}z 6∈L_{prime}.

### Some more examples using pumping lemma-I

Consider L_{prime} ={1^{p}|p is a prime number.}.

I For eachn, letw = 1^{p} such thatp >n+ 2
I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.

w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{p−j−i}

| {z }

z

I So, for any k≥0, we have|xy^{k}z|= (p−j) +kj.

I Choose k =p−j. Therefore,|xy^{k}z|= (p−j)(1 +j).
I Now (p−k)>1 and 1 +j >1, which impliesxy^{k}z 6∈L_{prime}.

### Some more examples using pumping lemma-I

Consider L_{prime} ={1^{p}|p is a prime number.}.

I For eachn, letw = 1^{p} such thatp >n+ 2
I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.

w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{p−j−i}

| {z }

z

I So, for any k≥0, we have|xy^{k}z|= (p−j) +kj.
I Choose k =p−j. Therefore,|xy^{k}z|= (p−j)(1 +j).

I Now (p−k)>1 and 1 +j >1, which impliesxy^{k}z 6∈L_{prime}.

### Some more examples using pumping lemma-I

Consider L_{prime} ={1^{p}|p is a prime number.}.

I For eachn, letw = 1^{p} such thatp >n+ 2
I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.

w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{p−j−i}

| {z }

z

I So, for any k≥0, we have|xy^{k}z|= (p−j) +kj.
I Choose k =p−j. Therefore,|xy^{k}z|= (p−j)(1 +j).

I Now (p−k)>1 and 1 +j >1, which impliesxy^{k}z 6∈L_{prime}.

### Some more examples using pumping lemma-II

Exercise

Consider L={1^{m}^{2}|m≥0}.

I For eachn, letw = 1^{n}^{2}

I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.
w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{n}^{2}^{−j−i}

| {z }

z

I So, |xy^{k}z|= (n^{2}−j) +kj.

I Let k = 2. Therefore,|xy^{k}z|=n^{2}+j.
I Since 0<j ≤n,n^{2} <n^{2}+j <n^{2}+ 2n+ 1.

Therefore, xy^{2}z 6∈L.

### Some more examples using pumping lemma-II

Exercise

Consider L={1^{m}^{2}|m≥0}.

I For eachn, letw = 1^{n}^{2}

I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.
w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{n}^{2}^{−j−i}

| {z }

z

I So, |xy^{k}z|= (n^{2}−j) +kj.

I Let k = 2. Therefore,|xy^{k}z|=n^{2}+j.
I Since 0<j ≤n,n^{2} <n^{2}+j <n^{2}+ 2n+ 1.

Therefore, xy^{2}z 6∈L.

### Some more examples using pumping lemma-II

Exercise

Consider L={1^{m}^{2}|m≥0}.

I For eachn, letw = 1^{n}^{2}

I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.
w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{n}^{2}^{−j−i}

| {z }

z

I So, |xy^{k}z|= (n^{2}−j) +kj.

I Let k = 2. Therefore,|xy^{k}z|=n^{2}+j.
I Since 0<j ≤n,n^{2} <n^{2}+j <n^{2}+ 2n+ 1.

Therefore, xy^{2}z 6∈L.

### Some more examples using pumping lemma-II

Exercise

Consider L={1^{m}^{2}|m≥0}.

I For eachn, letw = 1^{n}^{2}

I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.

w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{n}^{2}^{−j−i}

| {z }

z

I So, |xy^{k}z|= (n^{2}−j) +kj.

I Let k = 2. Therefore,|xy^{k}z|=n^{2}+j.
I Since 0<j ≤n,n^{2} <n^{2}+j <n^{2}+ 2n+ 1.

Therefore, xy^{2}z 6∈L.

### Some more examples using pumping lemma-II

Exercise

Consider L={1^{m}^{2}|m≥0}.

I For eachn, letw = 1^{n}^{2}

I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.

w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{n}^{2}^{−j−i}

| {z }

z

I So,|xy^{k}z|= (n^{2}−j) +kj.

I Let k = 2. Therefore,|xy^{k}z|=n^{2}+j.
I Since 0<j ≤n,n^{2} <n^{2}+j <n^{2}+ 2n+ 1.

Therefore, xy^{2}z 6∈L.

### Some more examples using pumping lemma-II

Exercise

Consider L={1^{m}^{2}|m≥0}.

I For eachn, letw = 1^{n}^{2}

I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.

w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{n}^{2}^{−j−i}

| {z }

z

I So,|xy^{k}z|= (n^{2}−j) +kj.

I Let k = 2. Therefore,|xy^{k}z|=n^{2}+j.

I Since 0<j ≤n,n^{2} <n^{2}+j <n^{2}+ 2n+ 1.
Therefore, xy^{2}z 6∈L.

### Some more examples using pumping lemma-II

Exercise

Consider L={1^{m}^{2}|m≥0}.

I For eachn, letw = 1^{n}^{2}

I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.

w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{n}^{2}^{−j−i}

| {z }

z

I So,|xy^{k}z|= (n^{2}−j) +kj.

I Let k = 2. Therefore,|xy^{k}z|=n^{2}+j.
I Since 0<j ≤n,n^{2}<n^{2}+j <n^{2}+ 2n+ 1.

Therefore, xy^{2}z 6∈L.

### Some more examples using pumping lemma-II

Exercise

Consider L={1^{m}^{2}|m≥0}.

I For eachn, letw = 1^{n}^{2}

I The first n characters ofw are 1^{n}.

I Let x= 1^{i} andy = 1^{j}, wherei+j ≤n andj 6= 0.

w = 1^{i}

|{z}x

1^{j}

|{z}y

1^{n}^{2}^{−j−i}

| {z }

z

I So,|xy^{k}z|= (n^{2}−j) +kj.

I Let k = 2. Therefore,|xy^{k}z|=n^{2}+j.
I Since 0<j ≤n,n^{2}<n^{2}+j <n^{2}+ 2n+ 1.

Therefore, xy^{2}z 6∈L.

### Some more examples using pumping lemma-III

Example of pumping down!

Is this regular: L={0^{`}1^{m}|` >m}?

I For eachn, letw = 0^{n}1^{n}

I Any breakup ofw hasx= 0^{i} andy = 0^{j}, wherei+j ≤n andj 6= 0.
w = 0^{i}

|{z}x

0^{j}

|{z}y

0^{n−j−i}1^{n}

| {z }

z

I if k >2, we getxy^{k}z = 0^{i}0^{j+2}0^{n−j−i}1^{n}∈L, so NOT enough!
I However, let k= 0 (pumping down). Then,xy^{k}z = 0^{i}0^{n−j−i}1^{n}6∈L.
I This completes the proof.

### Some more examples using pumping lemma-III

Example of pumping down!

Is this regular: L={0^{`}1^{m}|` >m}?

I For eachn, letw = 0^{n}1^{n}

I Any breakup ofw hasx= 0^{i} andy = 0^{j}, wherei+j ≤n andj 6= 0.
w = 0^{i}

|{z}x

0^{j}

|{z}y

0^{n−j−i}1^{n}

| {z }

z

I if k >2, we getxy^{k}z = 0^{i}0^{j+2}0^{n−j−i}1^{n}∈L, so NOT enough!
I However, let k= 0 (pumping down). Then,xy^{k}z = 0^{i}0^{n−j−i}1^{n}6∈L.
I This completes the proof.

### Some more examples using pumping lemma-III

Example of pumping down!

Is this regular: L={0^{`}1^{m}|` >m}?

I For eachn, letw = 0^{n}1^{n}

I Any breakup ofw hasx= 0^{i} andy = 0^{j}, wherei+j ≤n andj 6= 0.

w = 0^{i}

|{z}x

0^{j}

|{z}y

0^{n−j−i}1^{n}

| {z }

z

I if k >2, we getxy^{k}z = 0^{i}0^{j+2}0^{n−j−i}1^{n}∈L, so NOT enough!
I However, let k= 0 (pumping down). Then,xy^{k}z = 0^{i}0^{n−j−i}1^{n}6∈L.
I This completes the proof.

### Some more examples using pumping lemma-III

Example of pumping down!

Is this regular: L={0^{`}1^{m}|` >m}?

I For eachn, letw = 0^{n}1^{n}

I Any breakup ofw hasx= 0^{i} andy = 0^{j}, wherei+j ≤n andj 6= 0.

w = 0^{i}

|{z}x

0^{j}

|{z}y

0^{n−j−i}1^{n}

| {z }

z

I if k>2, we getxy^{k}z = 0^{i}0^{j+2}0^{n−j−i}1^{n} ∈L, so NOT enough!

I However, let k= 0 (pumping down). Then,xy^{k}z = 0^{i}0^{n−j−i}1^{n}6∈L.
I This completes the proof.

### Some more examples using pumping lemma-III

Example of pumping down!

Is this regular: L={0^{`}1^{m}|` >m}?

I For eachn, letw = 0^{n}1^{n}

I Any breakup ofw hasx= 0^{i} andy = 0^{j}, wherei+j ≤n andj 6= 0.

w = 0^{i}

|{z}x

0^{j}

|{z}y

0^{n−j−i}1^{n}

| {z }

z

I if k>2, we getxy^{k}z = 0^{i}0^{j+2}0^{n−j−i}1^{n} ∈L, so NOT enough!

I However, letk = 0 (pumping down). Then,xy^{k}z = 0^{i}0^{n−j}^{−i}1^{n}6∈L.

I This completes the proof.

### Some more examples using pumping lemma-III

Example of pumping down!

Is this regular: L={0^{`}1^{m}|` >m}?

I For eachn, letw = 0^{n}1^{n}

I Any breakup ofw hasx= 0^{i} andy = 0^{j}, wherei+j ≤n andj 6= 0.

w = 0^{i}

|{z}x

0^{j}

|{z}y

0^{n−j−i}1^{n}

| {z }

z

I if k>2, we getxy^{k}z = 0^{i}0^{j+2}0^{n−j−i}1^{n} ∈L, so NOT enough!

I However, letk = 0 (pumping down). Then,xy^{k}z = 0^{i}0^{n−j}^{−i}1^{n}6∈L.

I This completes the proof.

### Some more examples using pumping lemma-IV

Using regularity properties
Is this regular: L={0^{`}1^{m}|`6=m}?

I SupposeL is regular. Note that Σ ={0,1}.

I Consider the language L^{0} =L∩0^{∗}1^{∗}, where Lis the complement of L.
I This must be regular by closure properties.

I But L^{0} ={0^{n}1^{n}|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^{`}1^{m}|`6=m}?

I SupposeL is regular. Note that Σ ={0,1}.

I Consider the language L^{0} =L∩0^{∗}1^{∗}, where Lis the complement of L.
I This must be regular by closure properties.

I But L^{0} ={0^{n}1^{n}|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^{`}1^{m}|`6=m}?

I SupposeL is regular. Note that Σ ={0,1}.

I Consider the language L^{0} =L∩0^{∗}1^{∗}, where Lis the complement of L.

I This must be regular by closure properties.

I But L^{0} ={0^{n}1^{n}|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^{`}1^{m}|`6=m}?

I SupposeL is regular. Note that Σ ={0,1}.

I Consider the language L^{0} =L∩0^{∗}1^{∗}, where Lis the complement of L.

I This must be regular by closure properties.

^{0} ={0^{n}1^{n}|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^{`}1^{m}|`6=m}?

I SupposeL is regular. Note that Σ ={0,1}.

I Consider the language L^{0} =L∩0^{∗}1^{∗}, where Lis the complement of L.

I This must be regular by closure properties.

I But L^{0} ={0^{n}1^{n}|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{0^{n}1^{n}|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 {0^{n}1^{n}|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 {0^{n}1^{n}|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={ca^{n}b^{n}|n≥0}

| {z }

L1

∪ {c^{k}w|k 6= 1 andw ∈ {a,b}^{∗}}

| {z }

L2

Applying contrapositive of pumping lemma:
I For L_{1}, the long enough word has to be ca^{n}.

I But then, consider the partition of w =xyz wherex =,y =c
I Then if you pump up , i.e., c^{k}a^{n}b^{n}∈L_{2} ⊆L

I And if you pump down, i.e., c^{0}a^{n}b^{n}=a^{n}b^{n}∈L2 ⊆L
I And of course, i.e.,c^{1}a^{n}b^{n}∈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={ca^{n}b^{n}|n≥0}

| {z }

L1

∪ {c^{k}w|k 6= 1 andw ∈ {a,b}^{∗}}

| {z }

L2

Applying contrapositive of pumping lemma:

I For L_{1}, the long enough word has to be ca^{n}.

I But then, consider the partition of w =xyz wherex =,y =c
I Then if you pump up , i.e., c^{k}a^{n}b^{n}∈L_{2} ⊆L

I And if you pump down, i.e., c^{0}a^{n}b^{n}=a^{n}b^{n}∈L2 ⊆L
I And of course, i.e.,c^{1}a^{n}b^{n}∈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={ca^{n}b^{n}|n≥0}

| {z }

L1

∪ {c^{k}w|k 6= 1 andw ∈ {a,b}^{∗}}

| {z }

L2

Applying contrapositive of pumping lemma:

I For L_{1}, the long enough word has to be ca^{n}.

I But then, consider the partition of w =xyz wherex=,y =c

I Then if you pump up , i.e., c^{k}a^{n}b^{n}∈L_{2} ⊆L

I And if you pump down, i.e., c^{0}a^{n}b^{n}=a^{n}b^{n}∈L2 ⊆L
I And of course, i.e.,c^{1}a^{n}b^{n}∈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={ca^{n}b^{n}|n≥0}

| {z }

L1

∪ {c^{k}w|k 6= 1 andw ∈ {a,b}^{∗}}

| {z }

L2

Applying contrapositive of pumping lemma:

I For L_{1}, the long enough word has to be ca^{n}.

I But then, consider the partition of w =xyz wherex=,y =c
I Then if you pump up , i.e., c^{k}a^{n}b^{n}∈L_{2} ⊆L

^{0}a^{n}b^{n}=a^{n}b^{n}∈L2 ⊆L
I And of course, i.e.,c^{1}a^{n}b^{n}∈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={ca^{n}b^{n}|n≥0}

| {z }

L1

∪ {c^{k}w|k 6= 1 andw ∈ {a,b}^{∗}}

| {z }

L2

Applying contrapositive of pumping lemma:

I For L_{1}, the long enough word has to be ca^{n}.

I But then, consider the partition of w =xyz wherex=,y =c
I Then if you pump up , i.e., c^{k}a^{n}b^{n}∈L_{2} ⊆L

I And if you pump down, i.e., c^{0}a^{n}b^{n}=a^{n}b^{n}∈L2 ⊆L

I And of course, i.e.,c^{1}a^{n}b^{n}∈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={ca^{n}b^{n}|n≥0}

| {z }

L1

∪ {c^{k}w|k 6= 1 andw ∈ {a,b}^{∗}}

| {z }

L2

Applying contrapositive of pumping lemma:

I For L_{1}, the long enough word has to be ca^{n}.

I But then, consider the partition of w =xyz wherex=,y =c
I Then if you pump up , i.e., c^{k}a^{n}b^{n}∈L_{2} ⊆L

^{0}a^{n}b^{n}=a^{n}b^{n}∈L2 ⊆L
I And of course, i.e.,c^{1}a^{n}b^{n}∈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={ca^{n}b^{n}|n≥0}

| {z }

L1

∪ {c^{k}w|k 6= 1 andw ∈ {a,b}^{∗}}

| {z }

L2

Applying contrapositive of pumping lemma:

I For L_{1}, the long enough word has to be ca^{n}.

^{k}a^{n}b^{n}∈L_{2} ⊆L

^{0}a^{n}b^{n}=a^{n}b^{n}∈L2 ⊆L
I And of course, i.e.,c^{1}a^{n}b^{n}∈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 thatuxy^{k}zv 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 thatuxy^{k}zv 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 thatuxy^{k}zv 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 thatuxy^{k}zv 6∈L.

### More generalized pumping lemma

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 thatuxy^{k}zv 6∈L.

### More generalized pumping lemma

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 thatuxy^{k}zv 6∈L.

### More generalized pumping lemma

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 thatuxy^{k}zv 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

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 thatuxy^{k}zv 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

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 thatuxy^{k}zv 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,Σ, δ,q_{0},F)
I For all x,y ∈Σ^{∗}, we define

I x ≡_{A}y 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,Σ, δ,q_{0},F)
I For all x,y ∈Σ^{∗}, we define

I x ≡_{A}y 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,Σ, δ,q_{0},F)
I For all x,y ∈Σ^{∗}, we define

I x ≡_{A}y 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,Σ, δ,q_{0},F)
I For all x,y ∈Σ^{∗}, we define

I x ≡_{A}y 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,Σ, δ,q_{0},F)
I For all x,y ∈Σ^{∗}, we define

I x ≡_{A}y 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,Σ, δ,q_{0},F)
I For all x,y ∈Σ^{∗}, we define

I x ≡_{A}y 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 ≡

_{A}

I 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 ≡

_{A}

I 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 ≡

_{A}

I 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 ≡

_{A}

I 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 ≡

_{A}

I 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 ≡

_{A}

I 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 ≡

_{A}

I 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?