GATEverse Practice, past papers & mock tests
GATE 2027: 115 days Sign in Create account
GATE 2018
Theory of ComputationTuring Machine: RE, REC and UndecidabilityhardMCQ2 marks
Consider the following problems. L(G) denotes the language generated by grammar G. L(M) denotes the language accepted by machine M. (I) For an unrestricted grammar G and a string w, whether w ∈ L(G) (II) Given a Turing machine M, whether L(M) is regular (III) Given two grammars G1 and G2, whether L(G1) = L(G2) (IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language. Which one of the following statements is correct?
Save your progress

Related Theory of Computation PYQs

GATE 2018

Consider the following languages: I. { a^m b^n c^p d^q | m + p = n + q, where m, n, p, q >= 0 } II. { a^m b^n c^p d^q | m = n and …

GATE 2018

Given a language L, define L^0 = {ε}, L^i = L^(i-1) L. The order of language L is the smallest k such that L^k = L^(k+1). For lang…

GATE 2018

Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following…

GATE 2018

The set of all recursively enumerable languages is:

GATE 2026 · CS1 - Forenoon

Consider the following grammar where S is the start symbol, and a and b are terminal symbols. S → aSbS | bS | ε Which of the follo…

GATE 2026 · CS1 - Forenoon

Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be …