Recursive-and-Recursively-Enumerable-Language

Question 1

Nobody knows yet if P = NP. Consider the language L defined as follows:

Which of the following statements is true?

A
L is recursive
B
L is recursively enumerable but not recursive
C
L is not recursively enumerable
D
Whether L is recursive or not will be known after we find out if P = NP
Theory-of-ComputationRecursive-and-Recursively-Enumerable-LanguageGATE 2003
Question 1 Explanation: 
Here, we have two possibilities, whether
P = NP (or) P != NP
→ If P=NP then L=(0+1)* which is regular, then it is recursive.
→ If P!=NP then L becomes ɸ which is also regular, then it is recursive.
So, finally L is recursive.
Question 2

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
Theory-of-ComputationRecursive-and-Recursively-Enumerable-LanguageGATE 2004
Question 2 Explanation: 
Given that
L1 = recursively enumerable language
L2 over Σ∪{#} as {wi#wj | wi, wj ∈ L1, i < j}
S1 is True.
If L1 is recursive then L2 is also recursive. Because, to check w = wi#wj belongs to L2, and we give wi and wj to the corresponding decider L1, if both are to be accepted, then w∈L1 and not otherwise.
S2 is also True:
With the corresponding decider L2 we need to make decide L1.
Question 3
Let <M> denote an encoding of an automaton M. Suppose that Σ = {0,1}. Which of the following languages is/are NOT recursive?
A
L = { | M is a DFA such that L(M) = Σ*}
B
L = { | M is a DFA such that L(M) = ∅}
C
L = { | M is a PDA such that L(M) = Σ*}
D
L = { | M is a PDA such that L(M) = ∅}
Theory-of-ComputationRecursive-and-Recursively-Enumerable-LanguageGATE 2021 CS-Set-1Video-Explanation
Question 3 Explanation: 
Question 4

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

A
B
C
D
Theory-of-ComputationRecursive-and-Recursively-Enumerable-LanguageGATE 2005
Question 4 Explanation: 
Recursive languages are closed under complementation.
But, recursive enumerable languages are not closed under complementation.
If L1 is recursive, then L1', is also recursive.
If L2 is recursive enumerable, then L2', is not recursive enumerable language.
There are 4 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access