Register

GATE CSE 2004 | Question: 89

18,287 views
68 68 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

6 Answers

Best answer
73 73 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
7 7 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)

 

1 1 vote

To evaluate the assertions presented, we can analyze the relationships between the languages and the enumerator algorithm $A$.

 

Analyzing $S_1$: If $L_1$ is recursive, $L_2$ is recursive If $L_1$ is a recursive language, there exists a Turing machine that can decide whether any given string belongs to $L_1$ in a finite amount of time. To decide whether a string $u\#v$ belongs to $L_2$:

 

  1. Use the decider for $L_1$ to check if $u \in L_1$ and $v \in L_1$. If either string is not in $L_1$, reject $u\#v$.

  2. If both are confirmed to be in $L_1$, we know the enumerator algorithm $A$ will eventually output both $u$ and $v$.

  3. Run the enumerator $A$ until both $u$ and $v$ are produced, and record their respective positions in the sequence ($i$ and $j$). This process is guaranteed to halt because we already verified both strings are valid members of $L_1$.

  4. If $i < j$, accept the string; otherwise, reject it. Because this procedure will always halt and correctly decide membership for any string, $L_2$ is recursive. Assertion $S_1$ is true.

Analyzing $S_2$: If $L_2$ is recursive, $L_1$ is recursive Assume $L_2$ is a recursive language. To decide if an arbitrary string $x$ belongs to $L_1$:

 

  1. If $L_1$ is empty, it is trivially recursive.

  2. If $L_1$ is not empty, run the enumerator algorithm $A$ until it outputs its very first string, which we will call $\omega_1$. By definition, this string is at position $i = 1$.

  3. For any input string $x$ being tested, first check if $x = \omega_1$. If it is, accept it.

  4. If $x \neq \omega_1$, construct the new string $\omega_1\#x$. Because $\omega_1$ is the first string enumerated, any other valid string in $L_1$ must appear later in the sequence (at some index $j > 1$). Therefore, $x$ is in $L_1$ if and only if $\omega_1\#x$ is in $L_2$.

  5. Use the decider for $L_2$ to check the string $\omega_1\#x$. Because $L_2$ is recursive, this test is guaranteed to halt and will perfectly decide whether $x$ belongs to $L_1$.

    Because we can construct a halting decider for $L_1$ using the decider for $L_2$, $L_1$ is recursive. Assertion $S_2$ is true.

Both $S_1$ and $S_2$ are true statements. Therefore, option A is the correct answer.

• edited by
0 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
0 0 votes
L1 is recursive enumerable which is subsequently recursive. L2 is the union of L1 and # where # act is regular which will becomes recursive and we know that recursive union recursive is recursive. So both L1 and L2 are recursive that will implies both the options correct. (A)
0 0 votes

S1 ​: L1​ is recursive implies L2​ is recursive

Since L1 is recursive there exists a decider for L1 which can halt and accept for members of L1 and halt and reject for non members of L1.

Now to prove L2 is also recursive we just need to veify whether we can construct a decider for L2 or not.

L2 Input: u # v
   │
   ▼
[ L1 Decider ] ──► (Checks if both u and v belong to L1)
   │
   ├─► If NO ──► Halt & REJECT immediately (Safe termination)
   │
   └─► If YES ──► Pass control to...
         │
         ▼
   [ Enumerator ] ──► (Prints words w1, w2, w3... until it hits u and v)
         │
         ├─► Hits 'u' first ──► Halt & ACCEPT (i < j)
         └─► Hits 'v' first ──► Halt & REJECT (i ≥ j)
 

We can clearly construct a decider for L2 therefore L2 is recursive. S1 is true...

 

Similarly to prove if L2 is recursive then L1 is recursive we just need to prove if we can construct a decider which halt and accepts for members of L1 and halt and reject for non members of L1. This can be done as follow using the help of L2 decider.

Input string: x
   │
   ▼
[ Get w1 from Enumerator ] 
   │
   ├──► Is x = w1? ──► YES ──► Halt & ACCEPT immediately
   │
   └──► NO ──► Construct string: y = w1 # x
                 │
                 ▼
          [ L2 Decider ] ──► (Checks if w1 # x is in L2)
                 │
                 ├──► If YES ──► Halt & ACCEPT x into L1
                 └──► If NO  ──► Halt & REJECT x from L1
 

Since a decider can be constructed for L1, therefore L1 is recursive. S2 is also true...

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2004 | Ques...Next → · GATE CSE 2004 | Ques...
← Previous in category · GATE CSE 2004 | Ques...Next in category → · find minimal dfa for...
Position:
Show:

Related questions

80 80 votes
13 answers 13 answers
22.8k
22.8k views
Kathleen asked Sep 18, 2014
22,767 views
GATE CSE 2004 | Question: 81
Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected gr...
92 92 votes
8 answers 8 answers
40.5k
40.5k views
Arjun asked Sep 8, 2014
40,492 views
GATE CSE 2003 | Question: 54
Define languages $L_0$ and $L_1$ as follows :$L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\} $$L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts o...
0 0 votes
0 0 answers
418
418 views
Rishi yadav asked Mar 17, 2019
418 views
Peter Linz Edition 5 Exercise 11.3 Question 2 (Page No. 296)
Find context-sensitive grammars for the following languages.$(a)$ $L=\{w: n_a(w) = n_b(w) = n_c(w)\}$.$(b)$ $L=\{w: n_a(w) = n_b(w) < n_c(w)\}$.
0 0 votes
0 0 answers
293
293 views
Rishi yadav asked Mar 17, 2019
293 views
Peter Linz Edition 5 Exercise 11.3 Question 1 (Page No. 296)
Find the context-sensitive grammars for the following languages.$\text{(a)}$ $L=\{a^{n+1}b^nc^{n-1} : n\geq 1\}$.$\text{(b)}$ $L=\{a^{n}b^nc^{2n} : n\geq 1\}$.$\text{(c)}...