L1 is a recursively enumerable language over Σ. An algorithm A effectively…
GATE · 2004 · CS
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 52 students.
Sign up free to check your answer
Sign up freeLoading lesson…