Chapter 2: Finite Automata and Regular Expressions


1.5 RELATIONS

Let A and B be the two sets; then the relationship R between A and B is nothing more than a set of ordered pairs ( a , b ) such that a is in A and b is in B , and a is related to b by relation R . That is:

R = { ( a , b ) a is in A and b is in B , and a is related to b by R }

For example, if A = { 0, 1 } and B = { 1, 2 }, then we can define a relation of ˜less than, denoted by < as follows :

A pair (1, 1) will not belong to the < relation, because one is not less than one. Therefore, we conclude that a relation R between sets A and B is the subset of A B .

If a pair ( a , b ) is in R , then aRb is true; otherwise , aRb is false.

A is called a "domain" of the relation, and B is called a "range" of the relation. If the domain of a relation R is a set A , and the range is also a set A , then R is called as a relation on set A rather than calling a relation between sets A and B . For example, if A = { 0, 1, 2 }, then a < relation defined on A will result in: < = { (0, 1), (0, 2), (1, 2) }.

1.5.1 Properties of the Relation

Let R be some relation defined on a set A . Therefore:

  1. R is said to be reflexive if aRa is true for every a in A ; that is, if every element of A is related with itself by relation R , then R is called as a reflexive relation.

  2. If every aRb implies bRa (i.e., when a is related to b by R , and if b is also related to a by the same relation R ), then a relation R will be a symmetric relation.

  3. If every aRb and bRc implies aRc , then the relation R is said to be transitive; that is, when a is related to b by R , and b is related to c by R , and if a is also related to c by relation R , then R is a transitive relation.

    If R is reflexive and transitive, as well as symmetric, then R is an equivalence relation.

Property Closure of a Relation

Let R be a relation defined on a set A , and if P is a set of properties, then the property closure of a relation R , denoted as P -closure, is the smallest relation, R ² , which has the properties mentioned in P . It is obtained by adding every pair ( a , b ) in R to R ² , and then adding those pairs of the members of A that will make relation R have the properties in P . If P contains only transitivity properties, then the P -closure will be called as a transitive closure of the relation, and we denote the transitive closure of relation R by R + ; whereas when P contains transitive as well as reflexive properties, then the P -closure is called as a reflexive-transitive closure of relation R , and we denote it by R *. R + can be obtained from R as follows:

For example, if:




Algorithms for Compiler Design
Algorithms for Compiler Design (Electrical and Computer Engineering Series)
ISBN: 1584501006
EAN: 2147483647
Year: 2005
Pages: 108
Authors: O G Kakde

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net