Lecture 14: Myhill Nerode relations and regularity

(1)

CS310 : Automata Theory 2020

Lecture 14: Myhill Nerode relations and regularity

Instructor: S. Akshay

IIT Bombay, India

11-02-2020

(2)

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.

(3)

Recap

(4)

Recap

(5)

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^kzv 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?

(6)

Generalized pumping lemma

Theorem

|xy| ≤n then

(7)

Generalized pumping lemma

Theorem

|xy| ≤n then

(8)

Generalized pumping lemma

Theorem

|xy| ≤n then

(9)

Generalized pumping lemma

Theorem

|xy| ≤n then

I In our earlier version of pumping lemma,u =.

(10)

Generalized pumping lemma

Theorem

|xy| ≤n then

I In our earlier version of pumping lemma,u =.

I This is not an iff either. What other properties of regular languages can

(11)

Properties of regular languages

Let L be a regular language recognized by A= (Q,Σ, δ,q₀,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.

(12)

Properties of regular languages

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.

Properties of ≡_A

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

(13)

Properties of regular languages

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

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))

(14)

Properties of regular languages

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

Properties of ≡A

3. The number of equivalence classes of ≡_A is finite. (finite index)

(15)

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₀,x) = ˆδ(q₀,y)

Properties of ≡_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.

(16)

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.

(17)

Myhill-Nerode relation

Right congruence

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.

(18)

Myhill-Nerode relation

Right congruence

Refinement

Finite index

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

(19)

Myhill-Nerode relation

Right congruence

Refinement

Finite index

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

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

(20)

Myhill-Nerode theorem

Theorem

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

(21)

Myhill-Nerode theorem

Theorem

Proof. =⇒

I IfL is regular, consider DFAAfor L.

(22)

Myhill-Nerode theorem

Theorem

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.

(23)

Myhill-Nerode theorem

Theorem

Proof. ⇐= Conversely,

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

(24)

Myhill-Nerode theorem

Theorem

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

(25)

Myhill-Nerode theorem

Theorem

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

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

(26)

Myhill-Nerode theorem

Theorem

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

I We will build A≡= (Q,Σ, δ,q₀,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.

(27)

Applications of Myhill-Nerode theorem-I

Consider L={aⁿbⁿ|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ⁿ] = [a^m] forn6=m.

I Butby right congruence[aⁿb^m] = [a^mb^m]

I Whichviolates refinement ofLsinceaⁿb^m6∈L anda^mb^m∈L I Hence contradiction.

(28)

Applications of Myhill-Nerode theorem-I

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ⁿ] = [a^m] forn6=m.

(29)

Applications of Myhill-Nerode theorem-I

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

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

(30)

Applications of Myhill-Nerode theorem-I

I Suppose there werefinite many equiv classes.

I There exist [aⁿ] = [a^m] forn6=m. I Butby right congruence[aⁿb^m] = [a^mb^m]

(31)

Applications of Myhill-Nerode theorem-I

I There exist [aⁿ] = [a^m] forn6=m.

(32)

Applications of Myhill-Nerode theorem-I

(33)

Applications of Myhill-Nerode theorem-I

I Whichviolates refinement ofLsinceaⁿb^m6∈Landa^mb^m∈L I Hence contradiction.

(34)

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.

(35)

Applications of Myhill-Nerode theorem-II

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!]

(36)

Applications of Myhill-Nerode theorem-II

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!]

(37)

Applications of Myhill-Nerode theorem-II

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!]

(38)

Applications of Myhill-Nerode theorem-II

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!]

(39)

Applications of Myhill-Nerode theorem-II

(40)

Applications of Myhill-Nerode theorem-II

(41)

Applications of Myhill-Nerode theorem-II

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

(42)

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!

(43)

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]

Try more examples!

(44)

Applications of Myhill-Nerode theorem-III

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]

Try more examples!

(45)

Applications of Myhill-Nerode theorem-III

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

Try more examples!

(46)

Applications of Myhill-Nerode theorem-III

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

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

Try more examples!

(47)

Applications of Myhill-Nerode theorem-III

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

Try more examples!

(48)

Applications of Myhill-Nerode theorem-III

Try more examples!

(49)

Applications of Myhill-Nerode theorem-III

Try more examples!

(50)

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₀,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.

(51)

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

Theorem

(52)

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

Theorem

(53)

Applications of Myhill-Nerode Theorem-IV

I Thus, the DFA representationis not unique!

I What doesMyhill-Nerode construction give you?

Definition

Theorem

(54)

Applications of Myhill-Nerode Theorem-IV

Definition

Theorem

(55)

Applications of Myhill-Nerode Theorem-IV

Definition

In a DFA (Q,Σ, δ,q₀,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.