L1 is a Recursive Enumerable language over $\sum$.
An algorithm A effectively enumerates its words as w1,w2,w3...
Another language L2 is defined over ∑ U {#} such as {wi # wj | wi ,wj ∈ L1, i<j}
Consider the following assertions.
S1 : L1 is recursive implies L2 is recursive
S2 : L2 is recursive implies L1 is recursive
Which of the following statements is true.
(A) Both S1 and S2 are true.
(B) S1 is true but S2 is not necessarily true.
(C) S2 is true but S1 is not necessarily true.
(D) Neither is necessarily true.
