GATE Solved Paper 2017-19 - GATE 2017 Shift 2

11. Consider the set under the partial ordering R = {(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e),(c,c),(c,e),(d,d),(d,e),(e,e)}. The Hasse diagram of the partial order (X, R) is shown below.

The minimum number of ordered pairs that need to be added to R to make (X, R) a lattice is _____.

Note – Numerical Type question

  • Option : A
  • Explanation :
    A Hasse Diagram is called a Lattice, if for every pair of elements there exists a LUB and GLB.
    In the above Hasse Diagram, LUB and GUB exist for every two elements taken from {a,b,c,d,e}. So, it is already a Lattice.
    Hence, Minimum number of ordered pairs that need to be added =0
Cancel reply
Cancel reply

12. Which of the following statements about parser is/are CORRECT?
I. Canonical LR is more powerful than SLR
II. SLR is more powerful than LALR
III. SLR is more powerful than Canonical LR

  • Option : A
  • Explanation :
    Bottom up parsers in decreasing order of their power: CLR≫ LALR≫ SLR≫ LR (0)
    The given statements:
    I. Canonical LR is more powerful than SLR is CORRECT.
    II. SLR is more powerful than LALR is INCORRECT
    III. SLR is more powerful than Canonical LR is INCORRECT.
Cancel reply
Cancel reply

13. Match the following:

P. Static char var;i. Sequence of memory locations to store addresses
Q. m = malloc (10);
m = NULL:
ii. A variable located in data section of memory
R. R. char * ptr [10]iii. Request to allocate a CPU register to store data
S. Register int var1;iv. A lost memory which  cannot be freed

  • Option : A
  • Explanation :
    P. static char var:
    var is defined as character variable whose associated storage class is static because of this it is given memory from data segment
    Q. m malloc(10);
    m = NULL;
    10 contiguous bytes of memory is allocated is address of first byte is stored in 'm' and later it is updated with NULL. Now we lost the address of first bytes of that chunk of memory completely. So we can't free that space as we need the address of first byte to free it up
    R. char * ptr [10]:
    ptr is an array of 10 pointers pointing to character variables.
    S. register int varl:
    Suggesting the complier to store the var1 “value” in CPU register.
Cancel reply
Cancel reply

14. Let L1, L2 be any two context free languages and R be any regular language. Then which of the following is/are CORRECT?
I. L1 ∪ L2is context – free
II. L1 is context – free
III. L1 - R is context – free
IV. L1 ∩ L2 is context – free

  • Option : B
  • Explanation :
    Given L1 and L2 are context free languages and R is a regular language.
    I. L1 ∪ L2 is context free is CORRECT, context free language are closed under union operation.
    II. L1 is context free is INCORRECT, context free languages are not closed under complement operation.
    III. L1 - R is Context free is CORRECT.
    L1 - R = L1R, Context free intersection Regular is always Context free.
    IV. L1 ∩ L2 is context free is INCORRECT; context free languages are not closed under complement operation.
Cancel reply
Cancel reply