# GATE Solved Paper 2017-19 - GATE 2018

• Option : B
• Explanation :
Type checking is done before parsing is clearly false because in compiler type checking is done after parsing phase.

Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

• A

θ(1), θ(1)  • B

θ(1), θ(n)  • C

θ(n), θ(1)  • D

θ(n), θ(n)  • Option : B
• Explanation :
For Enqueue operation, performs in a constant amount of time (i.e., Θ(1)) So, the options B is correct.

• A

closed under complementation  • B

closed under intersection  • C

a subset of the set of all recursive languages  • D

an uncountable set  • Option : B
• Explanation :
The Set of RE languages is closed under intersection, not closed under complementation, is not a subset of set of REC language, and is a countable set.

• A

I and II only  • B

II and III only  • C

I and III only  • D

I, II and III  • Option : D
• Explanation :
RISC processor characteristics:
1. It supports mode registers, so ALU operations are performed only on register data.
2. It supports fixed-length instructions.
3. It uses a hard-wired control unit.

• A

k ≥ 2n  • B

k ≥ n  • C

k ≤ n2  • D

k ≤ 2n  • Option : D
• Explanation :
n is a number of state of given nfa (may not be minimal) k is a number of states of equivalent min dfa. First, we have to convert nfa to dfa using a subset construction algorithm and we get an equivalent dfa which will have atmost 2n states. Then we can convert this dfa to a minimal dfa and get a minimal dfa with k states where k ≤ 2n.
Related Quiz.
GATE 2018