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.
PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2018
// 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.
| A | B | C |
| a1 | 2 | c1 |
| a2 | 4 | c1 |
| a3 | 4 | c1 |
| A | B | C |
| a1 | 2 | c1 |
| a2 | 4 | c1 |
| a3 | 4 | c1 |
| A | B | C |
| a1 | 2 | c1 |
| a2 | 4 | c1 |
| a3 | 4 | c1 |
| A | B | C |
| a1 | 2 | c1 |
| a2 | 4 | c1 |
| a3 | 4 | c1 |
| a4 | 6 | Null |
| a5 | 6 | Null |
| A | B | C |
| a1 | 2 | c1 |
| a2 | 4 | c1 |
| a3 | 4 | c1 |
29
In a system, there are three types of resources: E, F and G. Four processes P0, P1, P2 and P3 execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[P2, F] is the maximum number of instances of F that P2 would require. The number of instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation. Consider a state of the system with the Allocation matrix as shown below, and in which 3 instances of E and 3 instances of F are the only resources available.
| Allocation | Max | |||||||
| E | F | G | E | F | G | |||
| P0 | 1 | 0 | 1 | P0 | 4 | 3 | 1 | |
| P1 | 1 | 1 | 2 | P1 | 2 | 1 | 4 | |
| P2 | 1 | 0 | 3 | P2 | 1 | 3 | 3 | |
| P3 | 2 | 0 | 0 | P3 | 5 | 4 | 1 | |
From the perspective of deadlock avoidance, which one of the following is true?
- A The system is in safe state
- B The system is not in safe state, but would be safe if one more instance of E were available
- C The system is not in safe state, but would be safe if one more instance of F were available
- D The system is not in safe state, but would be safe if one more instance of G were available
| Max need | Current allocation | Current available | Remaining need | |||||||||
| E | F | G | E | F | G | E(3) | F(3) | G(0) | E | F | G | |
| P0 | 4 | 3 | 1 | 1 | 0 | 1 | 4 | 3 | 1 | 3 | 3 | 0 |
| P1 | 2 | 1 | 4 | 1 | 1 | 2 | 5 | 3 | 4 | 1 | 0 | 2 |
| P2 | 1 | 3 | 3 | 1 | 0 | 3 | 6 | 4 | 6 | 0 | 3 | 0 |
| P3 | 5 | 4 | 1 | 2 | 0 | 0 | 8 | 4 | 6 | 3 | 4 | 1 |
Total number of scalar multiplications are 48 + 75 + 50 + 2000 = 2173 and optimal parenthesis is ((F1(F2(F3 F4))) F5). As concluded, F3, F4 are explicitly computed pairs.
