Suppose we have a DFA D on an alphabet S. We can define a relation "~D" on "all" strings over S in this manner: x ~D y iff d'(q0,x) = d'(q0,y). d'() denotes the extended tr. func.


Now, let L be some language (not necessarily L(D)) on S. We can also define a relation "~L" on "all" strings over S in this manner: x ~L y iff for every string z in S, xz is in L iff yz is in L.


(a [1 points]) Prove that ~D is an equivalence relation.
(b [1 points]) Prove that ~L is an equivalence relation.
(c [2 points]) Suppose L = L(D). Then, ~D implies ~L, i.e., if for any pair of strings, x ~D y then x ~L y. Write a clear level-1 which summarizes your approach and what is the main claim that you prove.
(d [2 points]) Prove that the converse of (c) is not true, i.e., there may be a pair of strings x and y such that x ~L y but x ~D y.
(e [4 points]) What are the equivalence classes of ~L where L = set of binary strings containing 101 as a substring? You do not need to justify your answer, simply state the classes.