Recursive-and-Recursively-Enumerable-Language

Question 1
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 1 Explanation: 
Question 2

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 2 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 3

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 3 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 4

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that  reduces to W, and Z reduces to  (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

A
W can be recursively enumerable and Z is recursive.
B
W can be recursive and Z is recursively enumerable.
C
W is not recursively enumerable and Z is recursive.
D
W is not recursively enumerable and Z is not recursive.
Theory-of-ComputationRecursive-and-Recursively-Enumerable-LanguageGATE 2016 [Set-1]Video-Explanation
Question 4 Explanation: 
The rules are:
If A ≤ p B
Rule 1: If B is recursive then A is recursive
Rule 2: If B is recursively enumerable then A is recursively enumerable
Rule 3: If A is not recursively enumerable then B is not recursively enumerable
Since X is recursive and recursive language is closed under compliment, so is also recursive.
: By rule 3, W is not recursively enumerable.
: By rule 1, Z is recursive.
Hence, W is not recursively enumerable and Z is recursive.
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