Understanding Myhill-Nerode Theorem in Automata Theory

Slide Note

Myhill-Nerode theorem states that three statements are equivalent regarding the properties of a regular language: 1) L is the union of some equivalence classes of a right-invariant equivalence relation of finite index, 2) Equivalence relation RL is defined in a specific way, and 3) RL has finite index. The theorem's proof involves conditions that mutually imply each other, focusing on equivalence relations, regular languages, and the index of the relation.

bo Follow

Uploaded on Jul 23, 2024 | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

MYHILL NERODE THEOREM By Anusha Tilkam

Myhill Nerode Theorem: The following three statements are equivalent 1. 2. L is the union of some of the equivalence classes of a right invariant equivalence relation of finite index. 3. Let equivalence relation RL be defined by : xRLy iff for all z in * xz is in L exactly when yz is in L. Then RLis of finite index. The set L * is accepted by a FSA

Theorem Proof: There are three conditions: 1. Condition (i) implies condition (ii) 2. Condition (ii) implies condition (iii) 3. Condition (iii) implies condition (i)

Equivalence Relation A binary relation over a set X is an equivalence relation if it satisfies Reflexivity Symmetry Transitivity

Condition (i) implies condition (ii) Proof: Let L be a regular language accepted by a DFSA M = (Q, , ,q0,F). Define RMon * x RMy if (q0, x) = (q0, y) In order to show that its an equivalence relation it has to satisfy three properties.

(q0, x) = (q0, x) --- Reflexive If (q0, x) = (q0, y) then (q0, y) = (q0, x) --- Symmetry If (q0, x) = (q0, y) (q0, y) = (q0, z) then (q0, x) = (q0, z) --- Transitive

Index of an Equivalence relation: There are N states q0 q1 q2 qn-1 If This RMis an Equivalence Relation, Then the index of RM is at most the number of States of M

Right invariant If x RM y Then xz RM yz for any z * Then we say RM is Right invariant Proof: (q0 , x) = (q0 , y) (q0 , xz) = ( (q0 , x), z ) = ( (q0 , y), z ) = (q0 , yz) Therefore RM is right invariant

L is the union of sum of the equivalence classes of that relation. If the Equivalence Relation RM has n states. S0 , S1 , S2, , Si , .. , Sn-1 | | | | | q0 , q1 , q2 , .., qi , .. , qn-1

Condition (ii) implies condition (iii) : Proof: Let E be an equivalence relation as defined in (ii). We have to prove that E is a Refinement of RL. What is Refinement?

x E y | x,y to same equivalence class of E xz E yz | xz is related to yz for any z * L is the union of sum of the equivalence classes of E. If L contains this equivalence class then xz and yz are in L or it may not be in L. Then we can say that x RL y Hence it is proved that every equivalence class in E is an Equivalence class in RL Then we can say that E is a Refinement of RL E is of finite index Index of RL <= index of E therefore RL is of Finite index.

Example : DFA b b b a a q0 q2 q1 a L ={ w | w contains a stings having atleast one a ,no sequence of b} * is partioned into three equivalence class J0,J1,J2

J0 b bb J1 a ba babaa J2 aa aba babab so on so on ..so on J0 strings which do not contain an a J1 strings which contain odd number of a s J2 - strings which contain even number of a s L = J1 U J2

Condition (iii) implies condition (i) Proof: Then xwz RL ywz x RL y if xz L yz L Therefore if z = wz then xwz L ywz L for any w and z RL is right invariant Define an FSA M = (Q , , ,q0 ,F ) as follows: For each equivalence class of RL ,we have a state in Q . |Q | = index of RL Hence RL is Right invariant

If x * denote the Equivalence class of RL to which x to [x] q0 = [ ] belongs to initial state / one equivalence class. For symbol a ([x],a) = [xa] This definition is consistent because RL is right invariant. If xRL y then ([x],a) = [ya] Because x,y belong to same class and Right invariant. Therefore we can say that L is accepted by a FSA.

Example : J0 and J1 U J2 are the two equivalence classes in RL a,b b a J1 , J2 J0

To show that a given language is not Regular: L = {anbn |n>=1} Assume that L is Regular Then by Myhill Nerode theorem we can say that L is the union of sum of the Equivalence classes and etc a, aa,aaa,aaaa, .. Each of this cannot be in different equivalence classes. an ~ am for m n By Right invariance anbn ~ am bn for m n Hence contradiction The L cannot be regular.