Let L be a subset of {a,b}*
Define a relation R (R sub L) on S* as follows:
L
for All of x, y is a member of S*,
(x,y) are members of R if for all of z, xz are members of L iff yz are members of L
A) Show that R is an equivalence relation
B) Suppose L={a^i b^i where i >= 0}
What can you say about the index of R (number of classes)? is it finite or infinite?
Show some classes and elements in these classes to justify your answer?
c) Suppose L={a^i b^j where i,j >= 0}
What can you say about the index of R (number of classes)? is it finite or infinite?
Show some classes and elements in these classes to justify your answer?
D) Suppose L={a^i b^3i where i >= 0}
What can you say about the index of R (number of classes)? is it finite or infinite?
Show some classes and elements in these classes to justify your answer?
Note: ^ means to the power, so a^i means a to the power of i.