## CS310 : Automata Theory 2020

### Lecture 14: Myhill Nerode relations and regularity

Instructor: S. Akshay

IIT Bombay, India

11-02-2020

### Recap

I Automata and algebraic models: DFA, NFA,-NFA, 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 and limitations of regular languages

I Closure - under union, intersection, complementation, reversal I Pumping lemma.

I Examples of non-regular languages and how to show non-regularity using pumping lemma.

### Recap

I Automata and algebraic models: DFA, NFA,-NFA, 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 and limitations of regular languages

I Closure - under union, intersection, complementation, reversal I Pumping lemma.

I Examples of non-regular languages and how to show non-regularity using pumping lemma.

### Recap

I Automata and algebraic models: DFA, NFA,-NFA, 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 and limitations of regular languages

I Closure - under union, intersection, complementation, reversal I Pumping lemma.

I Examples of non-regular languages and how to show non-regularity using pumping lemma.

### 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 This is not an iff either. What other properties of regular languages can we use?

### 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 This is not an iff either. What other properties of regular languages can we use?

### 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 This is not an iff either. What other properties of regular languages can we use?

### 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 This is not an iff either. What other properties of regular languages can we use?

### 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 This is not an iff either. What other properties of regular languages can we use?

### 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 This is not an iff either. What other properties of regular languages can

### Properties of regular languages

Let L be a regular language recognized by A= (Q,Σ, δ,q_{0},F)

I For all x,y ∈Σ^{∗}, we definex≡_{A} y iff ˆδ(q0,x) = ˆδ(q0,y)
I That is, the state reached after x andy are the same.

≡_{A} is anequivalence relation.

### Properties of regular languages

Let L be a regular language recognized by A= (Q,Σ, δ,q_{0},F)

I For all x,y ∈Σ^{∗}, we definex≡_{A} y iff ˆδ(q0,x) = ˆδ(q0,y)
I That is, the state reached after x andy are the same.

≡_{A} is anequivalence relation.

Properties of ≡_{A}

1. ∀x,y∈Σ^{∗} andw ∈Σ^{∗} ifx≡_{A} y thenx·w ≡_{A} y·w (right congruence)

### Properties of regular languages

Let L be a regular language recognized by A= (Q,Σ, δ,q_{0},F)

I For all x,y ∈Σ^{∗}, we definex≡_{A} y iff ˆδ(q0,x) = ˆδ(q0,y)

≡_{A} is anequivalence relation.

Properties of ≡A

1. ∀x,y∈Σ^{∗} andw ∈Σ^{∗} ifx≡_{A} y thenx·w ≡_{A} y·w (right congruence)
2. if x≡_{A} y then x ∈L(A) iff y ∈L(A) (refines L(A))

### Properties of regular languages

Let L be a regular language recognized by A= (Q,Σ, δ,q_{0},F)

I For all x,y ∈Σ^{∗}, we definex≡_{A} y iff ˆδ(q0,x) = ˆδ(q0,y)

≡_{A} is anequivalence relation.

Properties of ≡A

1. ∀x,y∈Σ^{∗} andw ∈Σ^{∗} ifx≡_{A} y thenx·w ≡_{A} y·w (right congruence)
2. if x≡_{A} y then x ∈L(A) iff y ∈L(A) (refines L(A))

3. The number of equivalence classes of ≡_{A} is finite. (finite index)

### Properties of regular languages

Let L be a regular language recognized by A= (Q,Σ, δ,q0,F)

I For all x,y ∈Σ^{∗}, we definex≡_{A} y iff ˆδ(q_{0},x) = ˆδ(q_{0},y)

≡_{A} is anequivalence relation.

Properties of ≡_{A}

1. ∀x,y∈Σ^{∗} andw ∈Σ^{∗} ifx≡_{A} y thenx·w ≡_{A} y·w (right congruence)
2. if x≡_{A} y then x ∈L(A) iff y ∈L(A) (refines L(A))

3. The number of equivalence classes of ≡_{A} is finite. (finite index)

An equivalence relation on Σ^{∗} satisfying the above three properties is called a
Myhill-Nerode relation.

### Myhill-Nerode relation

Right congruence

An equivalence relation ≡on Σ^{∗} is called aright congruenceif∀x,y ∈Σ^{∗}
and w ∈Σ^{∗} x ≡y =⇒ x·w ≡y·w.

Refinement

An equivalence relation≡on Σ^{∗} is said torefine a a languageLif x≡y
thenx ∈Liff y ∈L.

Finite index

An equivalence relation≡on Σ^{∗} is said to havefinite index if the number of
equivalence classes of≡is finite.

Myhill-Nerode relation

An equivalence relation≡is called aMyhill-Nerode relation for languageLif it is a right congruence, it refinesLand it is of finite index.

### Myhill-Nerode relation

Right congruence

An equivalence relation ≡on Σ^{∗} is called aright congruenceif∀x,y ∈Σ^{∗}
and w ∈Σ^{∗} x ≡y =⇒ x·w ≡y·w.

Refinement

An equivalence relation ≡on Σ^{∗} is said torefine a a languageLif x≡y
then x ∈Liff y ∈L.

Finite index

An equivalence relation≡on Σ^{∗} is said to havefinite index if the number of
equivalence classes of≡is finite.

Myhill-Nerode relation

An equivalence relation≡is called aMyhill-Nerode relation for languageLif it is a right congruence, it refinesLand it is of finite index.

### Myhill-Nerode relation

Right congruence

An equivalence relation ≡on Σ^{∗} is called aright congruenceif∀x,y ∈Σ^{∗}
and w ∈Σ^{∗} x ≡y =⇒ x·w ≡y·w.

Refinement

An equivalence relation ≡on Σ^{∗} is said torefine a a languageLif x≡y
then x ∈Liff y ∈L.

Finite index

An equivalence relation ≡on Σ^{∗} is said to havefinite index if the number of
equivalence classes of ≡is finite.

Myhill-Nerode relation

An equivalence relation≡is called aMyhill-Nerode relation for languageLif it is a right congruence, it refinesLand it is of finite index.

### Myhill-Nerode relation

Right congruence

^{∗} is called aright congruenceif∀x,y ∈Σ^{∗}
and w ∈Σ^{∗} x ≡y =⇒ x·w ≡y·w.

Refinement

An equivalence relation ≡on Σ^{∗} is said torefine a a languageLif x≡y
then x ∈Liff y ∈L.

Finite index

An equivalence relation ≡on Σ^{∗} is said to havefinite index if the number of
equivalence classes of ≡is finite.

Myhill-Nerode relation

An equivalence relation ≡is called aMyhill-Nerode relation for languageLif it is a right congruence, it refines Land it is of finite index.

### Myhill-Nerode theorem

Theorem

Let L⊆Σ^{∗}. L is regular iff there exists a Myhill-Nerode relation forL.

### Myhill-Nerode theorem

Theorem

Let L⊆Σ^{∗}. L is regular iff there exists a Myhill-Nerode relation forL.

Proof. =⇒

I IfL is regular, consider DFAAfor L.

### Myhill-Nerode theorem

Theorem

Let L⊆Σ^{∗}. L is regular iff there exists a Myhill-Nerode relation forL.

Proof. =⇒

I IfL is regular, consider DFAAfor L.

I As shown before ≡_{A} is an equivalence relation that is a right
congruence, refines Land of finite index.

I Thus ≡_{A} is a Myhill-Nerode relation forL.

### Myhill-Nerode theorem

Theorem

Let L⊆Σ^{∗}. L is regular iff there exists a Myhill-Nerode relation forL.

Proof. ⇐= Conversely,

I Suppose≡is a Myhill-Nerode relation for L.

### Myhill-Nerode theorem

Theorem

Let L⊆Σ^{∗}. L is regular iff there exists a Myhill-Nerode relation forL.

Proof. ⇐= Conversely,

I Suppose≡is a Myhill-Nerode relation for L.

I Let [x] ={y ∈Σ^{∗} |y ≡x}

### Myhill-Nerode theorem

Theorem

Let L⊆Σ^{∗}. L is regular iff there exists a Myhill-Nerode relation forL.

Proof. ⇐= Conversely,

I Suppose≡is a Myhill-Nerode relation for L.

I Let [x] ={y ∈Σ^{∗} |y ≡x}

I We will build A≡= (Q,Σ, δ,q0,F) for it.

### Myhill-Nerode theorem

Theorem

Let L⊆Σ^{∗}. L is regular iff there exists a Myhill-Nerode relation forL.

Proof. ⇐= Conversely,

I Suppose≡is a Myhill-Nerode relation for L.

I Let [x] ={y ∈Σ^{∗} |y ≡x}

I We will build A≡= (Q,Σ, δ,q_{0},F) for it.

I Q={[x]|x∈Σ^{∗}}
I q0= []

I [F] ={[x]|x∈L}

I δ([x],a) = [xa]

I Proof of correctness: By induction as always.

### Applications of Myhill-Nerode theorem-I

Consider L={a^{n}b^{n}|n ∈N}

I Consider an equiv relation ≡on{a,b}^{∗}

I Suppose it is a right congruence and it refines L. I Then, we will show it cannot have finite index.

I Suppose there werefinite many equiv classes.
I There exist [a^{n}] = [a^{m}] forn6=m.

I Butby right congruence[a^{n}b^{m}] = [a^{m}b^{m}]

I Whichviolates refinement ofLsincea^{n}b^{m}6∈L anda^{m}b^{m}∈L
I Hence contradiction.

### Applications of Myhill-Nerode theorem-I

Consider L={a^{n}b^{n}|n ∈N}

I Consider an equiv relation ≡on{a,b}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.
I Suppose there werefinite many equiv classes.
I There exist [a^{n}] = [a^{m}] forn6=m.

I Butby right congruence[a^{n}b^{m}] = [a^{m}b^{m}]

I Whichviolates refinement ofLsincea^{n}b^{m}6∈L anda^{m}b^{m}∈L
I Hence contradiction.

### Applications of Myhill-Nerode theorem-I

Consider L={a^{n}b^{n}|n ∈N}

I Consider an equiv relation ≡on{a,b}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.

I Suppose there werefinite many equiv classes.
I There exist [a^{n}] = [a^{m}] forn6=m.

I Butby right congruence[a^{n}b^{m}] = [a^{m}b^{m}]

I Whichviolates refinement ofLsincea^{n}b^{m}6∈L anda^{m}b^{m}∈L
I Hence contradiction.

### Applications of Myhill-Nerode theorem-I

Consider L={a^{n}b^{n}|n ∈N}

I Consider an equiv relation ≡on{a,b}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.

I Suppose there werefinite many equiv classes.

I There exist [a^{n}] = [a^{m}] forn6=m.
I Butby right congruence[a^{n}b^{m}] = [a^{m}b^{m}]

I Whichviolates refinement ofLsincea^{n}b^{m}6∈L anda^{m}b^{m}∈L
I Hence contradiction.

### Applications of Myhill-Nerode theorem-I

Consider L={a^{n}b^{n}|n ∈N}

I Consider an equiv relation ≡on{a,b}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.

I Suppose there werefinite many equiv classes.

I There exist [a^{n}] = [a^{m}] forn6=m.

I Butby right congruence[a^{n}b^{m}] = [a^{m}b^{m}]

I Whichviolates refinement ofLsincea^{n}b^{m}6∈L anda^{m}b^{m}∈L
I Hence contradiction.

### Applications of Myhill-Nerode theorem-I

Consider L={a^{n}b^{n}|n ∈N}

I Consider an equiv relation ≡on{a,b}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.

I Suppose there werefinite many equiv classes.

I There exist [a^{n}] = [a^{m}] forn6=m.

I Butby right congruence[a^{n}b^{m}] = [a^{m}b^{m}]

I Whichviolates refinement ofLsincea^{n}b^{m}6∈L anda^{m}b^{m}∈L
I Hence contradiction.

### Applications of Myhill-Nerode theorem-I

Consider L={a^{n}b^{n}|n ∈N}

I Consider an equiv relation ≡on{a,b}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.

I Suppose there werefinite many equiv classes.

I There exist [a^{n}] = [a^{m}] forn6=m.

I Butby right congruence[a^{n}b^{m}] = [a^{m}b^{m}]

I Whichviolates refinement ofLsincea^{n}b^{m}6∈Landa^{m}b^{m}∈L
I Hence contradiction.

### Applications of Myhill-Nerode theorem-II

Consider L={a^{n!} |n ∈N}

I Consider an equiv relation ≡on{a}^{∗}

I Suppose it is a right congruence and it refines L. I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.
I There exist [a^{n!}] = [a^{(n+k)!}] fork >0,n>1.
I But by right congruence [a^{n!}a^{n·n!}] = [a^{(n+k)!}a^{n·n!}]

I Which violates refinement ofLsince l.h.s∈Land r.h.s6∈L(show this!) I Hence contradiction.

Try the same for{1^{p}|p a prime} etc.

### Applications of Myhill-Nerode theorem-II

Consider L={a^{n!} |n ∈N}

I Consider an equiv relation ≡on{a}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.
I Suppose there were finite many equiv classes.
I There exist [a^{n!}] = [a^{(n+k)!}] fork >0,n>1.
I But by right congruence [a^{n!}a^{n·n!}] = [a^{(n+k)!}a^{n·n!}]

I Which violates refinement ofLsince l.h.s∈Land r.h.s6∈L(show this!) I Hence contradiction.

Try the same for{1^{p}|p a prime} etc.

### Applications of Myhill-Nerode theorem-II

Consider L={a^{n!} |n ∈N}

I Consider an equiv relation ≡on{a}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.
I There exist [a^{n!}] = [a^{(n+k)!}] fork >0,n>1.
I But by right congruence [a^{n!}a^{n·n!}] = [a^{(n+k)!}a^{n·n!}]

I Which violates refinement ofLsince l.h.s∈Land r.h.s6∈L(show this!) I Hence contradiction.

Try the same for{1^{p}|p a prime} etc.

### Applications of Myhill-Nerode theorem-II

Consider L={a^{n!} |n ∈N}

I Consider an equiv relation ≡on{a}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.

I There exist [a^{n!}] = [a^{(n+k)!}] fork >0,n>1.
I But by right congruence [a^{n!}a^{n·n!}] = [a^{(n+k)!}a^{n·n!}]

I Which violates refinement ofLsince l.h.s∈Land r.h.s6∈L(show this!) I Hence contradiction.

Try the same for{1^{p}|p a prime} etc.

### Applications of Myhill-Nerode theorem-II

Consider L={a^{n!} |n ∈N}

I Consider an equiv relation ≡on{a}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.

I There exist [a^{n!}] = [a^{(n+k)!}] fork >0,n>1.

I But by right congruence [a^{n!}a^{n·n!}] = [a^{(n+k)!}a^{n·n!}]

I Which violates refinement ofLsince l.h.s∈Land r.h.s6∈L(show this!) I Hence contradiction.

Try the same for{1^{p}|p a prime} etc.

### Applications of Myhill-Nerode theorem-II

Consider L={a^{n!} |n ∈N}

I Consider an equiv relation ≡on{a}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.

I There exist [a^{n!}] = [a^{(n+k)!}] fork >0,n>1.

I But by right congruence [a^{n!}a^{n·n!}] = [a^{(n+k)!}a^{n·n!}]

I Which violates refinement ofLsince l.h.s∈Land r.h.s6∈L(show this!) I Hence contradiction.

Try the same for{1^{p}|p a prime} etc.

### Applications of Myhill-Nerode theorem-II

Consider L={a^{n!} |n ∈N}

I Consider an equiv relation ≡on{a}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.

I There exist [a^{n!}] = [a^{(n+k)!}] fork >0,n>1.

I But by right congruence [a^{n!}a^{n·n!}] = [a^{(n+k)!}a^{n·n!}]

I Which violates refinement ofLsince l.h.s∈Land r.h.s6∈L(show this!) I Hence contradiction.

Try the same for{1^{p}|p a prime} etc.

### Applications of Myhill-Nerode theorem-II

Consider L={a^{n!} |n ∈N}

I Consider an equiv relation ≡on{a}^{∗}

I Suppose it is a right congruence and it refinesL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.

I There exist [a^{n!}] = [a^{(n+k)!}] fork >0,n>1.

I But by right congruence [a^{n!}a^{n·n!}] = [a^{(n+k)!}a^{n·n!}]

I Which violates refinement ofLsince l.h.s∈Land r.h.s6∈L(show this!) I Hence contradiction.

Try the same for {1^{p}|p a prime} etc.

### Applications of Myhill-Nerode theorem-III

Consider PAL={w ·w^{R} |w ∈Σ^{∗}}
I Consider an equiv relation ≡on Σ^{∗}

I Suppose it is a right congruence and it refines PAL. I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.
I There exist [x] = [y] forx 6=y,x,y∈Σ^{∗}.
I But by right congruence [x·x^{R}] = [y·x^{R}]

I Which violates refinement ofLsince l.h.s∈PALand r.h.s6∈PAL I Hence contradiction.

Try more examples!

### Applications of Myhill-Nerode theorem-III

Consider PAL={w ·w^{R} |w ∈Σ^{∗}}

I Consider an equiv relation ≡on Σ^{∗}

I Suppose it is a right congruence and it refinesPAL.

I Then, we will show it cannot have finite index.
I Suppose there were finite many equiv classes.
I There exist [x] = [y] forx 6=y,x,y∈Σ^{∗}.
I But by right congruence [x·x^{R}] = [y·x^{R}]

I Which violates refinement ofLsince l.h.s∈PALand r.h.s6∈PAL I Hence contradiction.

Try more examples!

### Applications of Myhill-Nerode theorem-III

Consider PAL={w ·w^{R} |w ∈Σ^{∗}}

I Consider an equiv relation ≡on Σ^{∗}

I Suppose it is a right congruence and it refinesPAL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.
I There exist [x] = [y] forx 6=y,x,y∈Σ^{∗}.
I But by right congruence [x·x^{R}] = [y·x^{R}]

I Which violates refinement ofLsince l.h.s∈PALand r.h.s6∈PAL I Hence contradiction.

Try more examples!

### Applications of Myhill-Nerode theorem-III

Consider PAL={w ·w^{R} |w ∈Σ^{∗}}

I Consider an equiv relation ≡on Σ^{∗}

I Suppose it is a right congruence and it refinesPAL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.

I There exist [x] = [y] forx 6=y,x,y∈Σ^{∗}.
I But by right congruence [x·x^{R}] = [y·x^{R}]

I Which violates refinement ofLsince l.h.s∈PALand r.h.s6∈PAL I Hence contradiction.

Try more examples!

### Applications of Myhill-Nerode theorem-III

Consider PAL={w ·w^{R} |w ∈Σ^{∗}}

I Consider an equiv relation ≡on Σ^{∗}

I Suppose it is a right congruence and it refinesPAL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.

I There exist [x] = [y] forx6=y,x,y∈Σ^{∗}.

I But by right congruence [x·x^{R}] = [y·x^{R}]

I Which violates refinement ofLsince l.h.s∈PALand r.h.s6∈PAL I Hence contradiction.

Try more examples!

### Applications of Myhill-Nerode theorem-III

Consider PAL={w ·w^{R} |w ∈Σ^{∗}}

I Consider an equiv relation ≡on Σ^{∗}

I Suppose it is a right congruence and it refinesPAL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.

I There exist [x] = [y] forx6=y,x,y∈Σ^{∗}.
I But by right congruence [x·x^{R}] = [y·x^{R}]

I Which violates refinement ofLsince l.h.s∈PALand r.h.s6∈PAL I Hence contradiction.

Try more examples!

### Applications of Myhill-Nerode theorem-III

Consider PAL={w ·w^{R} |w ∈Σ^{∗}}

I Consider an equiv relation ≡on Σ^{∗}

I Suppose it is a right congruence and it refinesPAL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.

I There exist [x] = [y] forx6=y,x,y∈Σ^{∗}.
I But by right congruence [x·x^{R}] = [y·x^{R}]

I Which violates refinement ofLsince l.h.s∈PALand r.h.s6∈PAL I Hence contradiction.

Try more examples!

### Applications of Myhill-Nerode theorem-III

Consider PAL={w ·w^{R} |w ∈Σ^{∗}}

I Consider an equiv relation ≡on Σ^{∗}

I Suppose it is a right congruence and it refinesPAL.

I Then, we will show it cannot have finite index.

I Suppose there were finite many equiv classes.

I There exist [x] = [y] forx6=y,x,y∈Σ^{∗}.
I But by right congruence [x·x^{R}] = [y·x^{R}]

I Which violates refinement ofLsince l.h.s∈PALand r.h.s6∈PAL I Hence contradiction.

Try more examples!

### Applications of Myhill-Nerode Theorem-IV

What are the properties of the automaton constructed from L

I ConsiderL to be all words with odd number ofa’s. I Does there exist another DFA accepting it?

I Thus, the DFA representationis not unique! I What doesMyhill-Nerode construction give you?

Definition

In a DFA (Q,Σ, δ,q_{0},F), statesp,q are called equivalent if for each wordw,
ˆδ(p,w) is accepting iff ˆδ(q,w) is accepting.

Theorem

GivenL, the DFA constructed from Lusing the Myhill-Nerode construction has minimum number of states possible.

### Applications of Myhill-Nerode Theorem-IV

What are the properties of the automaton constructed from L I ConsiderL to be all words with odd number ofa’s.

I Does there exist another DFA accepting it? I Thus, the DFA representationis not unique! I What doesMyhill-Nerode construction give you?

Definition

In a DFA (Q,Σ, δ,q_{0},F), statesp,q are called equivalent if for each wordw,
ˆδ(p,w) is accepting iff ˆδ(q,w) is accepting.

Theorem

GivenL, the DFA constructed from Lusing the Myhill-Nerode construction has minimum number of states possible.

### Applications of Myhill-Nerode Theorem-IV

What are the properties of the automaton constructed from L I ConsiderL to be all words with odd number ofa’s.

I Does there exist another DFA accepting it?

I Thus, the DFA representationis not unique! I What doesMyhill-Nerode construction give you?

Definition

In a DFA (Q,Σ, δ,q_{0},F), statesp,q are called equivalent if for each wordw,
ˆδ(p,w) is accepting iff ˆδ(q,w) is accepting.

Theorem

GivenL, the DFA constructed from Lusing the Myhill-Nerode construction has minimum number of states possible.

### Applications of Myhill-Nerode Theorem-IV

What are the properties of the automaton constructed from L I ConsiderL to be all words with odd number ofa’s.

I Does there exist another DFA accepting it?

I Thus, the DFA representationis not unique!

I What doesMyhill-Nerode construction give you?

Definition

_{0},F), statesp,q are called equivalent if for each wordw,
ˆδ(p,w) is accepting iff ˆδ(q,w) is accepting.

Theorem

### Applications of Myhill-Nerode Theorem-IV

I Does there exist another DFA accepting it?

I Thus, the DFA representationis not unique!

I What doesMyhill-Nerode construction give you?

Definition

_{0},F), statesp,q are called equivalent if for each wordw,
ˆδ(p,w) is accepting iff ˆδ(q,w) is accepting.

Theorem

### Applications of Myhill-Nerode Theorem-IV

I Does there exist another DFA accepting it?

I Thus, the DFA representationis not unique!

I What doesMyhill-Nerode construction give you?

Definition

In a DFA (Q,Σ, δ,q_{0},F), statesp,q are called equivalent if for each wordw,
δ(p,ˆ w) is accepting iff ˆδ(q,w) is accepting.

Theorem

Given L, the DFA constructed from Lusing the Myhill-Nerode construction has minimum number of states possible.