TOC |Gate-2018| Theory of Computation ( Automata)
1. 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 is necessarily true? [GATE – 2018]
a. k ≥ 2n
b. k ≥ n
c. k ≤ n2
d. k ≤ 2n
Answer : d)
2. The set of all recursively enumerable languages is : [GATE – 2018]
a. closed under complementation.
b. closed under intersection.
c. a subset of the set of all recursive languages.
d. an uncountable set.
Answer : b)
3. Given a language L, define Li as follows:
L0 = {ε}
Li = Li-1∙L for all i>0
The order of a language L is defined as the smallest k such that Lk = Lk+1.
Consider the language L1 (over alphabet 0) accepted by the following automaton. [GATE – 2018]
The order of L1 is ______.
a. 2
b. 3
c. 4
d. 5
Answer : a)
TOC |Gate-2018|
4. Consider the following languages:
I. {ambncpdq ∣ m + p = n + q, where m, n, p, q ≥ 0}
II. {ambncpdq ∣ m = n and p = q, where m, n, p, q ≥ 0}
III. {ambncpdq ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV. {ambncpdq ∣ mn = p + q, where m, n, p, q ≥ 0}
Which of the above languages are context-free? [GATE – 2018]
a. I and IV only
b. I and II only
c. II and III only
d. II and IV only
Answer : b)
TOC |Gate-2018|
5. Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M. [GATE – 2018]
(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 grammar 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 statement is correct?
a. Only I and II are undecidable
b. Only III is undecidable
c. Only I, II and III are undecidable
d. Only II and IV are undecidable
Answer : c)
OS – GATE Previous Year Questions
DS – GATE Previous Year Questions