Courses

# 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
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;