Chap7 Relations The Second Time Round.ppt

文档介绍：Chapter 7Relations: The Second Time Round
Wen-Hsiang Lu (盧文祥)
Department puter Science and Information Engineering,
National Cheng Kung University
2005/5/9
1
7. Relations: The Second Time Around
Introduction
Important relations:
Equivalence relation
Partial order
Application of equivalence relation
Minimization process: find a machine with the same function but fewer internal states.
2
7. Relations: The Second Time Around
Relations Revisited: Properties of Relations
Definition : For sets A, B, any subset of A  B is called a (binary) relation from A to B. Any subset of A  A is called a (binary) relation on A .
Example
Define the relation  on the set Z by ab, if a  b.
For x, yZ and nZ+, the modulo n relation  is defined by xy if x - y is a multiple of n, ., 92, -311, but 3  7
Example : Language A . For x, yA, define xy if x is a prefix of y.
3
7. Relations: The Second Time Around
Relations Revisited: Properties of Relations
Finite state machine M = (S, I, O, v, w)
Reachability
s1s2 if v(s1, x) = s2, xI.  denotes the first level of reachability.
s1s2 if v(s1, x1x2) = s2, x1x2 I2.  denotes the second level of reachability.
Equivalence
1-equivalence relation: s1E1s2 if w(s1, x) = w(s2, x) for xI.
k-equivalence relation: s1Eks2 if w(s1, y) = w(s2, y) for yIk.
If two states are k-equivalent for all k Z+, they are called equivalent.
4
7. Relations: The Second Time Around
Reflexive
Definition : A relation  on a set A is called reflexive if (x, x), for all xA.
Example : For A = {1, 2, 3, 4}, a relation  AA will be reflexive if and only if {(1, 1), (2, 2), (3, 3), (4, 4)}. But 1 = {(1, 1), (2, 2), (3, 3)} is not reflexive, 2 = {(x, y)| x  y, x, yA} is reflexive.
Example : Given a finite set A with A= n, we have AA= n2, so there are relations on A. Among them, are reflexive.
A = {a1, a2,…, an}
AA = {(ai, aj)|1  i, j n} = A1A2
A1 = {(ai, ai)|1  i  n}
A2 = {(ai, aj)|i  j, 1  i,