GATE Solved Paper 2017-19 - GATE 2017 Shift 1

51. Consider the language L given by the regular expression (a+b)*b(a+b) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automation (DFA) accepting L is ______.

  • Option : A
  • Explanation :
    The regular expression can be described as “All strings over {a, b} ending with “ba” or “bb”. The minimal DFA accepting L is having 4 states:
Cancel reply
Cancel reply

53. Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below:

ProcessArrival timeBurst time
P107
P233
P355
P462
If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is _______ milliseconds.


Note: Numerical Type question.

  • Option : C
  • Explanation :

    Turn Around Time
    P1 = 12-0 = 12
    P2 = 6-3 = 3
    P3 = 17-5 = 12
    P4 = 8 - 6 = 2
    Waiting Time
    P1 = 12-7 = 5
    P2 = 3-3 = 0
    P3 = 12-5 = 7
    P4 = 2 - 2 = 0
    Average Waiting time = (7+0+5+0)/4 = 3.0
    Therefore, option C is correct
Cancel reply
Cancel reply

55. Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _____.

  • Option : C
  • Explanation :
    Given, v= Total vertices = 10
    e = v – 1 =9
    Degree = 2 * e = 18
    Therefore, option C is correct
Cancel reply
Cancel reply