Equivalence DFA, NDFA - Sequential Machine Theory Computer Science Engineering (CSE) Notes | EduRev

Computer Science Engineering (CSE) : Equivalence DFA, NDFA - Sequential Machine Theory Computer Science Engineering (CSE) Notes | EduRev

 Page 1


Equivalence, DFA, NDFA
Sequential Machine Theory 
Prof. K. J. Hintz
Department of Electrical and Computer 
Engineering
Lecture 2
Updated and modified by Marek 
Perkowski
Page 2


Equivalence, DFA, NDFA
Sequential Machine Theory 
Prof. K. J. Hintz
Department of Electrical and Computer 
Engineering
Lecture 2
Updated and modified by Marek 
Perkowski
Equivalence Relation on A
• An Equivalence Relation (Not Relationship) 
Is Not an Equality Relation
• A Relation is an Equivalence Relation if 
and only if (iff) it is:
– Reflexive
– Symmetric
– Transitive
Page 3


Equivalence, DFA, NDFA
Sequential Machine Theory 
Prof. K. J. Hintz
Department of Electrical and Computer 
Engineering
Lecture 2
Updated and modified by Marek 
Perkowski
Equivalence Relation on A
• An Equivalence Relation (Not Relationship) 
Is Not an Equality Relation
• A Relation is an Equivalence Relation if 
and only if (iff) it is:
– Reflexive
– Symmetric
– Transitive
Equivalence Relation on A
( )
( ) ( )
( ) ( ) ( )
( ) A
A
A
A
 on ~ relation e equivalenc an is 
e) (transitiv  ' ' , ' , ' ' , ' ' , '  ' ,
) (symmetric                           ' , , '  ' ,
) (reflexive                                                     ' ,  ,
   
R
R R R,
R R
R
then
a a a a a a a a a
and
a a a a a a
and 
a a a a
if
? ? ? ? ? ?
? ? ? ? ?
? ? ?
Page 4


Equivalence, DFA, NDFA
Sequential Machine Theory 
Prof. K. J. Hintz
Department of Electrical and Computer 
Engineering
Lecture 2
Updated and modified by Marek 
Perkowski
Equivalence Relation on A
• An Equivalence Relation (Not Relationship) 
Is Not an Equality Relation
• A Relation is an Equivalence Relation if 
and only if (iff) it is:
– Reflexive
– Symmetric
– Transitive
Equivalence Relation on A
( )
( ) ( )
( ) ( ) ( )
( ) A
A
A
A
 on ~ relation e equivalenc an is 
e) (transitiv  ' ' , ' , ' ' , ' ' , '  ' ,
) (symmetric                           ' , , '  ' ,
) (reflexive                                                     ' ,  ,
   
R
R R R,
R R
R
then
a a a a a a a a a
and
a a a a a a
and 
a a a a
if
? ? ? ? ? ?
? ? ? ? ?
? ? ?
Non-Algebraic Equivalence 
Relation Example
Equivalence Relation on the Set of All 
Triangles on a Plane
“is congruent to” or “is similar to”
– Reflexive, each triangle is similar to itself,
Page 5


Equivalence, DFA, NDFA
Sequential Machine Theory 
Prof. K. J. Hintz
Department of Electrical and Computer 
Engineering
Lecture 2
Updated and modified by Marek 
Perkowski
Equivalence Relation on A
• An Equivalence Relation (Not Relationship) 
Is Not an Equality Relation
• A Relation is an Equivalence Relation if 
and only if (iff) it is:
– Reflexive
– Symmetric
– Transitive
Equivalence Relation on A
( )
( ) ( )
( ) ( ) ( )
( ) A
A
A
A
 on ~ relation e equivalenc an is 
e) (transitiv  ' ' , ' , ' ' , ' ' , '  ' ,
) (symmetric                           ' , , '  ' ,
) (reflexive                                                     ' ,  ,
   
R
R R R,
R R
R
then
a a a a a a a a a
and
a a a a a a
and 
a a a a
if
? ? ? ? ? ?
? ? ? ? ?
? ? ?
Non-Algebraic Equivalence 
Relation Example
Equivalence Relation on the Set of All 
Triangles on a Plane
“is congruent to” or “is similar to”
– Reflexive, each triangle is similar to itself,
Equivalence Relation Example
Symmetric, if                           
is similar to 
then
is similar to
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

ppt

,

practice quizzes

,

pdf

,

Equivalence DFA

,

past year papers

,

Sample Paper

,

Equivalence DFA

,

MCQs

,

Important questions

,

Viva Questions

,

mock tests for examination

,

NDFA - Sequential Machine Theory Computer Science Engineering (CSE) Notes | EduRev

,

Semester Notes

,

Extra Questions

,

Equivalence DFA

,

shortcuts and tricks

,

Objective type Questions

,

NDFA - Sequential Machine Theory Computer Science Engineering (CSE) Notes | EduRev

,

NDFA - Sequential Machine Theory Computer Science Engineering (CSE) Notes | EduRev

,

Exam

,

video lectures

,

Previous Year Questions with Solutions

,

Summary

,

Free

,

study material

;