GATEverse Practice, past papers & mock tests
GATE 2027: 115 days Sign in Create account
GATE 2015 · Set-1
Theory of ComputationTuring Machine: RE, REC and UndecidabilitymediumMCQ2 marks
For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true? 1. L1' (complement of L1) is recursive. 2. L2' (complement of L2) is recursive. 3. L1' is context-free. 4. L1' ∪ L2 is recursively enumerable.
Save your progress

Related Theory of Computation PYQs

GATE 2015 · Set-1

The number of states in the minimal deterministic finite automaton (DFA) accepting the language L = {w in {0, 1}* | w contains '01…

GATE 2015 · Set-2

Consider the languages L1 = {a^n b^m c^n+m | n, m >= 1} and L2 = {a^n b^m | n, m >= 0}. Which of the following statements is TRUE?

GATE 2015 · Session-1

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the foll…

GATE 2015 · Session-1

See the question below and answer

GATE 2015 · Session-2

GATE 2015 CS - Set 2 - Question 20: see question below and answer

GATE 2015 · Session-2

GATE 2015 CS - Set 2 - Question 45: see question below and answer