GATE Solved Paper 2017-19 - GATE 2018

26. Consider the following languages:
I {ambncpdq | m + p = n + q, where m, n, p, q ≥ 0}
II {ambncpdq | m = n and p = q, where m, n, p, q ≥ 0}
III {ambncpdq | m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV {ambncpdq | mn = p + q, where m, n, p, q ≥ 0}
Which of the language above are context-free?

  • Option : B
  • Explanation :
    I {ambncpdq | m + p = n + q} is clearly CFL since, we can rearrange the equation as m - n + p - q = 0 which can be done by push, pop, and pop and check if stack is empty at end.
    II {ambncpdq | m = n and p = q} is clearly CFL since, one comparison at a time can be done by pda
    III {ambncpdq | m = n = p and p ≠ q} is not CFL since m = n = p is a double comparison which cannot be done by PDA.
    IV {ambncpdq | mn = p + q} is not a CFL, since mn involves multiplying number of a’s and number b’s which cannot be done by a PDA.
    So, only I and II are CFL’s.
Cancel reply
Cancel reply

27. Consider the following C code. Assume that unsigned long int type length is 64 bits.
Unsigned long int fun (unsigned long int n)
{
unsigned long int i, j = 0, sum = 0;
for (I = n; I > 1; I = i/2) j++;
for (; j > 1; j = j/2) sum++;
return (sum);
}
The value returned when we call fun with the input 240 is

  • Option : B
  • Explanation :
    // n takes 2^40
    unsigned long int fun(unsigned long int n) {
    // initialized sum = 0
    unsigned long int i, j, sum = 0;
    //First it takes i = n = 2^40,
    //then it divides i by 2 and incremented once j
    //each time, that's will make makes j = 40,
    for( i=n; i>1; i=i/2) j++;
    //Now the value of j = 40,
    //it divides j by 2 and incremented once sum
    //each time, that's will make makes sum = 5,
    for( ; j>1; j=j/2) sum++;
    //returns sum = 5
    return sum;
    }
    So, answer is 5.
Cancel reply
Cancel reply

28. Consider the relations r(A, B) and s(B, C), where s.B is a primary key and r.B is a foreign key referencing s.B. Consider the query Q: r⋈(σB<5(s)) Let LOJ denote the natural left outer-join operation. Assume that r and s contain no null values.

  • Option : C
  • Explanation :

    Given query: r ⋈ ( σB<5(s))
    ABC
    a12c1
    a24c1
    a34c1

    A: σB<5(r ⋈ s)
    ABC
    a12c1
    a24c1
    a34c1

    B:  σB<5(r ⋈ s)
    ABC
    a12c1
    a24c1
    a34c1

    C: r ⋈ (σB<5(s))
    ABC
    a12c1
    a24c1
    a34c1
    a46Null
    a56Null

    D: σ;B<5 (r) ⋈  s
    ABC
    a12c1
    a24c1
    a34c1

    Option “C” query result not equal to given query.
Cancel reply
Cancel reply