GATEverse Practice, past papers & mock tests
GATE 2027: 115 days Sign in Create account
GATE 2015 · Session-1
Theory of ComputationTuring Machine: RE, REC and UndecidabilitymediumMCQ1 mark
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? I. Complement(L1) is recursive II. Complement(L2) is recursive III. Complement(L1) is context-free IV. Complement(L1) ∪ L2 is recursively enumerable
Save your progress

Related Theory of Computation PYQs

GATE 2015 · Set-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 · 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

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