Question

Give a formal proof: show that A* is a reflexive and transitive set containing A.

Answer 1

Reflexive means A is related to itself i.e. aRa. In other words, we can say that if the set contains only single elements then it must contain A and if set contained elements in pair of two then there should be AA and so on. As given it contains A* so it contains all possible pairs of A.so that will be  Reflexive sets.

Transitive means if aRb and bRc then aRc must hold for transitivity i.e. if A related B and B related to C then for transitive set A must be related to C.But we have given only a single alphabet i.e. A.

To check transitivity condition there must be two condition valid i.e. aRb and bRc then only we need to check for aRc for transitivity but as from above the first two conditions is not satisfying so we do not need to check for the third condition. The string is already a transitive set.