GATE Solved Paper 2017-19 - GATE 2017 Shift 1

31. If G is grammar with productions
S → SAS | aSb | bSa | SS | ∈
where S is the start variable,
then which one of the following is not generated by G?

  • Option : D
  • Explanation :
    1) S → SS → aSbS → abS → abaSb → abab
    2) S → aSb → aSaSb → aaaSb → aaab
    3) S → SS → aSbS → abS → abaSb → abab → abbSaSa → abbaa
    4) can't not drive
Cancel reply
Cancel reply

32. The value of

Cancel reply
Cancel reply

33. Consider a database that has the relation schemas EMP (EmpId, EmpName, DepId), and DEPT(DeptName, DeptId). Note that the DepId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.
I. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∀ v ∈ DEPT (t[DeptId] ≠ DeptId]))}
II. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] ≠ DeptId]))}
III. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] = DeptId]))}

  • Option : D
  • Explanation : Given, DepId can be permitted to be NULL
    I. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∀ v ∈ DEPT (t[DeptId] ≠ DeptId]))} : Gives empnames who donot belong to any department
    II. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] ≠ DeptId]))} : Gives empnames who donot belong to some department
    III. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] = DeptId]))}: Gives empnames who donot belong to same department
    All of these queries are giving some results which are finite and thus all are safe expressions.
    Therefore, option D is correct.
Cancel reply
Cancel reply

34. Recall that Belady’s anomaly is that the pages-fault rate may increase as the number of allocated frames increases. Now consider the following statements:
S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady’s anomaly
S2: LRU page replacement algorithm suffers from Belady’s anomaly
Which of the following is CORRECT?

  • Option : B
  • Explanation :
    Statement 1 is “TRUE”. Because there can be a case when page selected to be replaced is by FIFO policy.
    Statement 2 is “FALSE”. Because LRU page replacement algorithm does not suffers from Belady’s Anomaly. Only FIFO page replacement algorithm suffers from Belady’s Anomaly.
Cancel reply
Cancel reply