10,956 views
52 votes
52 votes

$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?

  1. Both $S_1$ and $S_2$ are true

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

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

  4. Neither is necessarily true

3 Answers

Best answer
54 votes
54 votes

$S_1$ is TRUE.

If $L_1$ is recursive $L_2$ must also be recursive. Because to check if a word $w = w_i\#w_j$ belong to $L_2$, we can give $w_i$ and $w_j$ to the decider for $L_1$ and if both are accepted then $w$ belong to $L_1$ and not otherwise.

$S_2$ is TRUE.

With a decider for $L_2$ we can make a decider for $L_1$ as follows. Let $w_1$ be the first string enumerated by algorithm $A$ for $L_1$. Now, to check if a word $w$ belongs to $L_1$, make a string $w' = w_1\#w$ and give it to the decider for $L_2$ and if accepted, then $w$ belongs to $L_1$ and not otherwise.

So, answer must be A.

PS: For the second part, the given construction can fail if $L_1$ happens to be a finite language (more specifically if $L_1$ is empty). But all finite languages are anyway decidable.

edited by
3 votes
3 votes

1. Recursive languages are closed under concatenation.  

2. Recursive languages are closed under quotient with regular language. 

Let's assume

L3 = {#}. ------> regular because finite. Hence recursive.

L4= L1.L3 = {wi# : wi belongs to L1)

L4 is recursive. (1) 

L5= {#}.L1 ----> recursive (1)

S1: given L1 is recursive

Therefore L2=L4.L1 is also recursive. (1)

Hence S1 is true.

S2: given L2 is recursive

Therefore L1= L2/L5 is also recursive. (2)

S2 is true as well. 

 

ANSWER: (a)

 

0 votes
0 votes
Basically if L1 is recursive then L2 is union of L1’s. Hence L2 is also recursive. This is because recursive U recursive is recursive. Hence both S1 and S2 is true. So option A is true
Answer:

Related questions

0 votes
0 votes
0 answers
3
Rishi yadav asked Apr 9, 2019
192 views
Consider the set of machine language instructions for a computer of your choice. Sketch how the various instructions in this set could be carried out by a Turing machine....