# TOC |Gate-2018| Previous Year Questions| Set-3

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

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.

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

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

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