Multiple choice

L1 is a recursively enumerable language over$\sum$. An algorithm A effectively enumerates its words as w1,w2,w3,.... Define another language L2 over $\sum \cup$ {#} as {wi # wj: wi, wj $\in$ L1, i < j}. Here # is a new symbol. Consider the following assertion. S1:L1 is recursive implies L2 is recursive S2:L2 is recursive implies L1 is recursive

Which of the following statements is true?

  1. Both S1 and S2 are true

  2. S1 is true but S2 is not necessarily true

  3. S2 is true but S1 ins necessarily true

  4. Neither is necessarily true
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Keep practicing — related questions