L1 is a recursively enumerable language over Σ. An algorithm A effectively…
2004
L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, ... Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, i < j}. Here # is a new symbol. 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
Attempted by 7 students.
Show answer & explanation
Correct answer: A
S1 is true because if L1 is recursive, we can effectively enumerate its words and decide membership in finite time. This allows us to construct a decider for L2 by checking if wi and wj are in L1 and i < j. S2 is true because if L2 is recursive, we can guarantee that all words in L1 are generated or that membership in L1 can be decided, as the enumeration of wi will cover all elements of L1. Therefore, S2 imply that L1 is recursive.
A video solution is available for this question — log in and enroll to watch it.