-
L1 is a recursively enumerable language over ∑. An algorithm A effectively enumerates its words as W1, W2, W3,... define another language L2 over ∑ ∪ {#} as {Wi # Wj: W1, 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?
-
- Both S1 and S2 are true
- S1 is true but S2 is not necessarily true
- S2 is true but S1 is not necessarily true
- Neither is necessarily true
- Both S1 and S2 are true
Correct Option: A
S1 is TRUE.
If L1 is recursive L2 must also be recursive. Because to check. If a word w = wi #wj belong to L2, we can give wiwj to the decider for L1 and if both are accepted then w belong to L1 and not otherwise. S2 is TRUE.
With a decider for L2 we can make a decider for L1 as follows. Let w1 be the first string enumerated by algorithm A for L1. Now, to check if a word w belongs to L1, make a string w' = w1 # w and give it to the decider for L2 and if accepted, then w belongs to L1 and not otherwise. So, answer must be A.
