Myhill-Nerode Theorem in Automata Theory
undefined
MYHILL NERODE THEOREM
By
Anusha Tilkam
Myhill Nerode Theorem:
The following three statements are equivalent
1.
The set L
є
∑* is accepted by a FSA
2.
L is the union of some of the equivalence classes of a
right invariant equivalence relation of finite index.
3.
Let equivalence relation R
L
be defined by :
xR
L
y iff for all z in ∑* xz is in L exactly when yz is in L.
Then R
L
is of finite index.
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,∑,
δ
,q
0
,F).
Define R
M
on ∑*
x R
M
y if
δ
(q
0
, x) =
δ
(q
0
, y)
In order to show that its an equivalence relation it
has to satisfy three properties.
•
δ
(q
0
, x) =
δ
(q
0
, x) --- Reflexive
•
If
δ
(q
0
, x) =
δ
(q
0
, y) then
δ
(q
0
, y) =
δ
(q
0
, x) --- Symmetry
•
If
δ
(q
0
, x) =
δ
(q
0
, y)
δ
(q
0
, y) =
δ
(q
0
, z) then
δ
(q
0
, x) =
δ
(q
0
, z) --- Transitive
•
Index of an Equivalence relation:
There are N states
If This R
M
is an Equivalence Relation, Then the
index of R
M
is at most the
number of States of M
q
0
q
1
q
2
q
n-1
•
Right invariant
If x R
M
y
Then xz R
M
yz for any z
є
∑*
Then we say R
M
is Right invariant
Proof:
δ
(q
0
, x) =
δ
(q
0
, y)
δ
(q
0
, xz) =
δ
(
δ
(q
0
, x), z )
=
δ
(
δ
(q
0
, y), z )
=
δ
(q
0
, yz)
Therefore R
M
is right invariant
•
L is the union of sum of the equivalence classes of
that relation.
If the Equivalence Relation R
M
has n states.
S
0
, S
1
, S
2
, ……, S
i ,
…….. , S
n-1
| | | | |
q
0
, q
1
, q
2
,….., q
i
,…..…, q
n-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 R
L
.
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 R
L
y
Hence it is proved that every equivalence class in E is an
Equivalence class in R
L
Then we can say that E is a Refinement of R
L
E is of finite index
Index of R
L
<= index of E
therefore R
L
is of Finite index.
•
Example : DFA
L ={ w | w contains a stings having atleast one a ,nosequence of b}
∑* is partioned into three equivalence class J
0
,J
1
,J
2
q
0
q
1
q
2
b
b
a
a
b
a
J
0
– strings which do not contain an a
J
1
– strings which contain odd number of a’s
J
2
- strings which contain even number of a’s
L = J
1
U J
2
•
Condition (iii) implies condition (i)
Proof:
R
L
is right invariant
x R
L
y if xz
є
L yz
є
L
Therefore if z = wz then
xwz
є
L ywz
є
L for any w and z
Then xwz R
L
ywz
Hence R
L
is Right invariant
Define an FSA M’ = (Q’, ∑,
δ
’,q
0
’
,F’) as follows:
For each equivalence class of R
L
,we have a state in Q’.
|Q’| = index of R
L
•
If x
є
∑* denote the Equivalence class of R
L
to which x
є
to
[x]
q
0
’ = [
є
] belongs to initial state / one equivalence class.
For symbol a
є
∑
δ
’([x],a) = [xa]
This definition is consistent because R
L
is right invariant.
If xR
L
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 :
J
0
and J
1
U J
2
are the two equivalence classes in
R
L
J
0
J
1
, J
2
b
a,b
a
To show that a given language is not
Regular:
•
L = {an
b
n
|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.
a
n
~ a
m
for m ≠ n
By Right invariance
a
n
b
n
~ a
m
b
n
for m ≠ n
Hence contradiction
The L cannot be regular.
Conclusion
•
Shown how the Myhill Nerode theorem helps in
minimizing the number of states in a DFA.
•
How it shows that the language is not regular.
References
•
Languages and Machines
Thomas A. Sudkamp, Addison Wesley
•
http://en.wikipedia.org/wiki/Myhill%E2%80%9
3Nerode_theorem
Thank You
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.
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.
Conclusion Shown how the Myhill Nerode theorem helps in minimizing the number of states in a DFA. How it shows that the language is not regular.
References Languages and Machines Thomas A. Sudkamp, Addison Wesley http://en.wikipedia.org/wiki/Myhill%E2%80%9 3Nerode_theorem
