# TOC |Gate-2015| Previous Year Questions| Set-6 TOC |Gate-2015| Theory of Computation ( Automata)

1. Which of the following languages are context-free? [GATE – 2015]

L1 = {ambnanbm ⎪ m, n ≥ 1}
L2 = {ambnambn ⎪ m, n ≥ 1}
L3 = {ambn ⎪ m = 2n + 1}

a. L1 and L2 only
b. L1 and L3 only
c. L2 and L3 only
d. L3 only

2. Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are True? [GATE – 2015]

I. If L4 ∈ P, L2 ∈ P
II. If L1 ∈ P or L3 ∈ P, then L2 ∈ P
III. L1 ∈ P, if and only if L3 ∈ P
IV. If L4 ∈ P, then L1 ∈ P and L3 ∈ P

a. II only
b. III only
c. I and IV only
d. I only

3. Let L be the language represented by the regular expression Σ*0011Σ* where Σ = {0,1} What is the minimum number of states  in a DFA that recognizes L’ (compliment of L)? [GATE – 2015]

a. 4
b. 5
c. 6
d. 7

4. The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1) * (10) is __________ [GATE – 2015]

a. 3
b. 4
c. 5
d. 6

5. Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is __________. [GATE – 2015]

a. 1
b. 2
c. 3
d. 4

6. Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is the set of states, Σ is the input alphabet, Γ is stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states, The state transition is as follows: Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton? [GATE – 2015]

a. 10110
b. 10010
c. 01010
d. 01001

7. Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with the above statement? [GATE – 2015]

a. Q1 is in NP, Q2 in NP hard
b. Q1 is in NP, Q2 is NP hard
c. Both Q1 and Q2 are in NP
d. Both Q1 and Q2 are NP hard

8. Consider the follwoing statements.

I. The compliment of every Turning Decidable language is Turning Decidable.
II. There exists some language which is in NP but not turning decidable
III. If L is a language in NP, L is turning decidable

Which of the above statement is/are true?[GATE – 2015]

a. Only II
b. Only III
c. Only I and II
d. Only I and III