Q89

MCQ2 marks, −0.5

$L_1$ is a recursively enumerable language over $\Sigma$ . An algorithm $A$ effectively enumerates its words as $\omega_1, \omega_2, \omega_3, \dots .$ Define another language $L_2$ over $\Sigma \cup \left\{\text{#}\right\}$ as $\left\{w_i \text{#} w_j \mid w_i, w_j \in L_1, i < j \right\}$ . Here # is new symbol. Consider the following assertions. $S_1:L_1$ is recursive implies $L_2$ is recursive $S_2:L_2$ is recursive implies $L_1$ is recursive Which of the following statements is true?

(A)

Both $S_1$ and $S_2$ are true

(B)

$S_1$ is true but $S_2$ is not necessarily true

(C)

$S_2$ is true but $S_1$ is not necessarily true

(D)

Neither is necessarily true

Loading…