Gate2006
Question 1 
Consider the polynomial p(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3}, where a_{i} ≠ 0, ∀_{i}. The minimum number of multiplications needed to evaluate p on an input x is:
3  
4  
6  
9 
Question 1 Explanation:
Given polynomial equation is
p(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} where a_{i}≠0
This can be written as
p(x) = a_{0} +x( a_{1} + a_{2}x + a_{3}x^{2})=a_{0}+(a_{1}+(a_{2}+a_{3}x)x)x
Total no. of multiplications required is 3
i.e., a_{3}x = K.....(i)
(a_{2}+K)x = M..... (ii)
(a_{1}+M)x=N...... (iii)
p(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} where a_{i}≠0
This can be written as
p(x) = a_{0} +x( a_{1} + a_{2}x + a_{3}x^{2})=a_{0}+(a_{1}+(a_{2}+a_{3}x)x)x
Total no. of multiplications required is 3
i.e., a_{3}x = K.....(i)
(a_{2}+K)x = M..... (ii)
(a_{1}+M)x=N...... (iii)
Question 2 
Let X, Y, Z be sets of sizes x, y and z respectively. Let W = X×Y and E be the set of all subsets of W. The number of functions from Z to E is:
Z^{2}^{xy}  
Z×2^{xy}  
Z^{2}^{x+y}  
2^{xyz} 
Question 2 Explanation:
A set consists of n elements then no. of possible subsets are 2^{n}.
A set ‘P’ consists of m elements and ‘Q’ consists of n elements then total number of function from P to Q is m^{n}.
⇒ E be the no. of subsets of W = 2^{w} = 2^{xxy} = 2^{xy}
No. of function from Z to E is = (2xy)^{z} = (2xy)^{z} = 2^{xyz}
A set ‘P’ consists of m elements and ‘Q’ consists of n elements then total number of function from P to Q is m^{n}.
⇒ E be the no. of subsets of W = 2^{w} = 2^{xxy} = 2^{xy}
No. of function from Z to E is = (2xy)^{z} = (2xy)^{z} = 2^{xyz}
Question 3 
The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false?
It is not closed
 
2 does not have an inverse
 
3 does not have an inverse
 
8 does not have an inverse

Question 3 Explanation:
The given set is x = {1,2,3,5,7,8,9}
Option A:
It is not closed under multiplication. After multiplication modulo (10) we get ‘0’. The ‘0’ is not present in the set.
(2*5)%10 ⇒ 10%10 = 0
Option B:
2 does not have an inverse such as
(2*x)%10 ≠ 1
Option C:
3 have an inverse such that
(3*7)%10 = 1
Option D:
8 does not have an inverse such that
(8*x)%10 ≠ 1
Option A:
It is not closed under multiplication. After multiplication modulo (10) we get ‘0’. The ‘0’ is not present in the set.
(2*5)%10 ⇒ 10%10 = 0
Option B:
2 does not have an inverse such as
(2*x)%10 ≠ 1
Option C:
3 have an inverse such that
(3*7)%10 = 1
Option D:
8 does not have an inverse such that
(8*x)%10 ≠ 1
Question 4 
Neither a Partial Order nor an Equivalence Relation
 
A Partial Order but not a Total Order
 
A Total Order
 
An Equivalence Relation

Question 4 Explanation:
If a relation is equivalence then it must be
i) Symmetric
ii) Reflexive
iii) Transitive
If a relation is partial order relation then it must be
i) Reflexive
ii) Antisymmetric
iii) Transitive
If a relation is total order relation then it must be
i) Reflexive
ii) Symmetric
iii) Transitive
iv) Comparability
Given ordered pairs are (x,y)R(u,v) if (xv).
Here <, > are using while using these symbol between (x,y) and (y,v) then they are not satisfy the reflexive relation. If they uses (x<=u) and (y>=u) then reflexive relation can satisfies.
So, given relation cannot be a Equivalence. Total order relation or partial order relation.
i) Symmetric
ii) Reflexive
iii) Transitive
If a relation is partial order relation then it must be
i) Reflexive
ii) Antisymmetric
iii) Transitive
If a relation is total order relation then it must be
i) Reflexive
ii) Symmetric
iii) Transitive
iv) Comparability
Given ordered pairs are (x,y)R(u,v) if (x
Here <, > are using while using these symbol between (x,y) and (y,v) then they are not satisfy the reflexive relation. If they uses (x<=u) and (y>=u) then reflexive relation can satisfies.
So, given relation cannot be a Equivalence. Total order relation or partial order relation.
Question 5 
For which one of the following reasons does Internet Protocol (IP) use the timeto live (TTL) field in the IP datagram header?
Ensure packets reach destination within that time  
Discard packets that reach later than that time
 
Prevent packets from looping indefinitely
 
Limit the time for which a packet gets queued in intermediate routers 
Question 5 Explanation:
It prevent infinite looping over network .Bcz each router decrease its value by one and when this(TTL) value become zero ,then it is discarded by router silently.
Question 6 
Consider three CPUintensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.
1  
2  
3  
4 
Question 6 Explanation:
Total no.of context switches is 2.
Question 7 
(i) and (ii)
 
(ii) and (iii)  
(i) and (iii)  
None of the above

Question 7 Explanation:
As we can see in the below given LR(0) items, that all three belongs to different state (sets).
Question 8 
You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flipflops) will delay the phase of f by 180°?
Question 8 Explanation:
Duty cycle is the period of time where the signal high, i.e. 1.
50% of duty cycle means, the wave is 1 for half of the time and 0 for the other half of the time. It is a usual digital signal with 1 and 0.
The waveform f changes for every negative edge, that means f value alters from 1 to 0 or 0 to 1 for every negative edge of the clock.
Now the problem is that we need to find the circuit which produces a phase shift of 180, which means the output is 0 when f is 1 and output is 1 when f is 0.
Like the below image.
Now to find the answer we can choose elimination method.
F changes for negative edge, so that output too should change at negative edge. i.e if f becomes 0, then at the same time output should become 1, vice versa.
So, whenever input changes, at the same point of time output too should change. As input changes on negative edge, the output should be changed at negative edge only.
To have the above behaviour, the second D flipflop which produces the final output should be negative edge triggered. because whatever the 2nd flipflop produces, that is the output of the complete circuit.
So, we can eliminate option a, d.
Now either b or c can be answer.
How the flipflop chain works in option b and c is as below.
—> F changes at negative edge.
—> But flipflop1 responds at next positive edge.
—> After this flipflop2 responds at next negative edge.
That means flipflop2 produces the same input which is given to flipflop now after a positive edge and a negative edge, that means a delay of one clock cycle, which is 180 degrees phase shift for the waveform of f.
Option b) we are giving f’, so that the output is f’ with 180 degrees phase shift.
Option c) we are giving f, so that the output is f with 180 degrees phase shift.
Hence option C is the answer.
50% of duty cycle means, the wave is 1 for half of the time and 0 for the other half of the time. It is a usual digital signal with 1 and 0.
The waveform f changes for every negative edge, that means f value alters from 1 to 0 or 0 to 1 for every negative edge of the clock.
Now the problem is that we need to find the circuit which produces a phase shift of 180, which means the output is 0 when f is 1 and output is 1 when f is 0.
Like the below image.
Now to find the answer we can choose elimination method.
F changes for negative edge, so that output too should change at negative edge. i.e if f becomes 0, then at the same time output should become 1, vice versa.
So, whenever input changes, at the same point of time output too should change. As input changes on negative edge, the output should be changed at negative edge only.
To have the above behaviour, the second D flipflop which produces the final output should be negative edge triggered. because whatever the 2nd flipflop produces, that is the output of the complete circuit.
So, we can eliminate option a, d.
Now either b or c can be answer.
How the flipflop chain works in option b and c is as below.
—> F changes at negative edge.
—> But flipflop1 responds at next positive edge.
—> After this flipflop2 responds at next negative edge.
That means flipflop2 produces the same input which is given to flipflop now after a positive edge and a negative edge, that means a delay of one clock cycle, which is 180 degrees phase shift for the waveform of f.
Option b) we are giving f’, so that the output is f’ with 180 degrees phase shift.
Option c) we are giving f, so that the output is f with 180 degrees phase shift.
Hence option C is the answer.
Question 9 
A CPU has 24bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?
400  
500  
600  
700 
Question 9 Explanation:
The instruction is of 24 bits or 3 bytes. Now the program starts at address 300 and the next will be 303 then, 306, then 309 and so on.
So finally we can say that the values in the program counter will always be the multiple of 3.
Hence, option (C) is correct.
So finally we can say that the values in the program counter will always be the multiple of 3.
Hence, option (C) is correct.
Question 10 
In a binary max heap containing n numbers, the smallest element can be found in time
O(n)  
O(log n)  
O(log log n)
 
O(1) 
Question 10 Explanation:
We have to search all the elements in max heap. So, the worst case time complexity for Max Heap is O(n).
Question 11 
Consider a weighted complete graph G on the vertex set {v_{1}, v_{2}, ... v_{n}} such that the weight of the edge (v_{i}, v_{j}) is 2i  j. The weight of a minimum spanning tree of G is:
n1  
2n2
 
n^{2} 
Question 11 Explanation:
1) Including the initial call which means write the length of the spanning tree, a simple one it is. (Based on a particular graph)
2)Weight of the minimum spanning tree = 22  1 + 23  2 + 24  3 + 25  4 .... + 2 n  (n1)  = 2n  2
2)Weight of the minimum spanning tree = 22  1 + 23  2 + 24  3 + 25  4 .... + 2 n  (n1)  = 2n  2
Question 12 
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
Queue  
Stack  
Heap  
BTree 
Question 12 Explanation:
Queue: Basically we do BFStraversal of the graph to get the shortest paths.There is no point of using Minheap if it is unweighted graph. Even though if you use after every extract min operation you have to do minheapify which takes O(log V) time. so, the total time will be O(VlogV). As it is undirected graph you should do BFS from the source then you will get shortest path only. It will take O(V+E) time.
Question 13 
A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.
log_{2}n  
n  
2n+1
 
2^{n}1

Question 13 Explanation:
The binary right skewed tree follows 2^{n} 1 because level 2 value is 7 and level 3 value 15.
Note: Assume level numbers are start with 0.
Note: Assume level numbers are start with 0.
Question 14 
Which one of the following in place sorting algorithms needs the minimum number of swaps?
Quick sort  
Insertion sort  
Selection sort
 
Heap sort 
Question 14 Explanation:
Selection sort requires minimum number of swaps i.e O(n). The algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list. It does no more than n swaps, and thus is useful where swapping is very expensive.
Question 15 
val(j) = θ(logn)  
val(j) = θ(√n)  
val(j) = θ(n)
 
val(j) = θ(n logn) 
Question 15 Explanation:
The loop following series is n/2 + n/4 + n/8 + .. + 1 = Θ(n).
Question 16 
Let S be an NPcomplete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomialtime reducible to R. Which one of the following statements is true?
R is NPcomplete
 
R is NPhard  
Q is NPcomplete
 
Q is NPhard

Question 16 Explanation:
NPHard if it can be solved in polynomial time then all NPComplete can be solved in polynomial time. If NP Hard problem is reducible to another problem in Polynomial Time, then that problem is also NP Hard which means every NP problem can be reduced to this problem in Polynomial Time.
Question 17 
An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array
Solves it in linear time using a left to right pass of the array
 
Solves it in linear time using a right to left pass of the array  
Solves it using divide and conquer in time θ(nlogn)
 
Solves it in time θ(n^{2}) 
Question 17 Explanation:
Solves it in linear time using a right to left pass of the array will takes time complexity is O(n).
Question 18 
1/n  
2  
√n  
n 
Question 18 Explanation:
The smallest element in sample S would be x_{i} for which i is the smallest.
The given probability P_{i} is for selection of each item independently with probability 1/2.
Now, Probability for x_{1} to be smallest in S = 1/2
Now, Probability for x_{2} to be smallest in S = Probability of x_{1} not being in S × Probability of x_{2} being in S
= 1/2 × 1/2
Similarly, Probability x_{i} to be smallest = (1/2)^{i}
Now the Expected value is
The given probability P_{i} is for selection of each item independently with probability 1/2.
Now, Probability for x_{1} to be smallest in S = 1/2
Now, Probability for x_{2} to be smallest in S = Probability of x_{1} not being in S × Probability of x_{2} being in S
= 1/2 × 1/2
Similarly, Probability x_{i} to be smallest = (1/2)^{i}
Now the Expected value is
Question 19 
L_{1} only  
L_{3} only
 
L_{1} and L_{2}
 
L_{2} and L_{3}

Question 19 Explanation:
L_{1} can be accepted by PDA, we need to push all 0’s before 1’s and when 1’s comes in input string we need to pop every 0’s from stack for every 1’s and then for every 0’s. If stack and input string is empty at the same time then the string belongs to L_{1}.
But for L_{2} and L_{3} PDA implementation is not possible. The reason is, in L_{2} there are two comparison at a time, first the number of 0’s in beginning should be equal to 1’s and then 0’s after 1’s must be less than or equal to number of 1’s. Suppose for initial 0’s and 1’s are matched by using stack then after matching stack will become empty and then we cannot determine the later 0’s are equal to or less than number of 1’s. Hence PDA implementation is not possible. Similarly L_{3} also has the similar reason.
But for L_{2} and L_{3} PDA implementation is not possible. The reason is, in L_{2} there are two comparison at a time, first the number of 0’s in beginning should be equal to 1’s and then 0’s after 1’s must be less than or equal to number of 1’s. Suppose for initial 0’s and 1’s are matched by using stack then after matching stack will become empty and then we cannot determine the later 0’s are equal to or less than number of 1’s. Hence PDA implementation is not possible. Similarly L_{3} also has the similar reason.
Question 20 
We must redo log record 6 to set B to 10500.
 
We must undo log record 6 to set B to 10000 and then redo log records 2 and 3.
 
We need not redo log records 2 and 3 because transaction T1 has committed.
 
We can apply redo and undo operations in arbitrary order because they are idempotent.

Question 20 Explanation:
When the database system crashes after the transactions have committed then we need to redo the log records. And if the database system crashes before the transactions have committed then we need to undo the log records.
So from above theory we can say that option (B) is the correct answer.
So from above theory we can say that option (B) is the correct answer.
Question 21 
For each element in a set of size 2n, an unbiased coin is tossed. The 2n coin tosses are independent. An element is chosen if the corresponding coin toss were head. The probability that exactly n elements are chosen is:
Question 21 Explanation:
Total number of coins = 2n
No. of elements selected = n
Probability of getting head = ½
Probability of n heads out of 2n coin tosses is
2nC_{n}*(1/2)^{n}*(1/2)^{n}=2nC_{n}/4^{n}
No. of elements selected = n
Probability of getting head = ½
Probability of n heads out of 2n coin tosses is
2nC_{n}*(1/2)^{n}*(1/2)^{n}=2nC_{n}/4^{n}
Question 22 
X ⊂ Y  
X ⊃ Y
 
X = Y  
X  Y ≠ ∅ and Y  X ≠ ∅

Question 22 Explanation:
Let us consider
E = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)}
F = {(1,1), (2,2), (3,3)}
G = {(1,3), (2,1), (2,3), (3,1)}
X = (E∩F)  (F∩G)
= {(1,1), (2,2), (3,3)  ∅}
= {(1,1), (2,2), (3,3)} (✔️)
Y = (E  (E∩G)  (E  F))
= (E  {(1,3), (2,3), (3,1)}  {(1,2), (1,3), (2,3), (3,1)})
= {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)}  {(1,3), (2,2), (2,1)}  (1,2), (1,3), (2,3), (3,1)}
= {(1,1), (1,2), (2,2), (3,3)}  {(1,2), (1,3), (2,3), (3,1)}
= {(1,1), (2,2), (3,3)} (✔️)
X = Y
X = (E∩F)  (F∩G) = {2,5}  {5} = {2}
Y = (E  (E∩G)  (E  F))
= {(1,2,4,5)  (4,5)  (1,4)}
= {(1,2)  (1,4)}
= {2}
X = Y
E = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)}
F = {(1,1), (2,2), (3,3)}
G = {(1,3), (2,1), (2,3), (3,1)}
X = (E∩F)  (F∩G)
= {(1,1), (2,2), (3,3)  ∅}
= {(1,1), (2,2), (3,3)} (✔️)
Y = (E  (E∩G)  (E  F))
= (E  {(1,3), (2,3), (3,1)}  {(1,2), (1,3), (2,3), (3,1)})
= {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,1)}  {(1,3), (2,2), (2,1)}  (1,2), (1,3), (2,3), (3,1)}
= {(1,1), (1,2), (2,2), (3,3)}  {(1,2), (1,3), (2,3), (3,1)}
= {(1,1), (2,2), (3,3)} (✔️)
X = Y
X = (E∩F)  (F∩G) = {2,5}  {5} = {2}
Y = (E  (E∩G)  (E  F))
= {(1,2,4,5)  (4,5)  (1,4)}
= {(1,2)  (1,4)}
= {2}
X = Y
Question 23 
Fis an n×n real matrix. b is an n×1 real vector. Suppose there are two n×1 vectors, u and v such that, u≠v and Fu=b, Fv=b. Which one of the following statements is false?
Determinant of F is zero  
There are an infinite number of solutions to Fx=b  
There is an x≠0 such that Fx=0  
F must have two identical rows 
Question 23 Explanation:
⇾ Fu = b, Fv = b
Fu = Fv
Fu  Fv = 0
F(u  v) = 0
Given u ≠ v
F = 0 (i.e., Singular matrix, so determinant is zero)
Option A is true.
⇾ Fx = b; where F is singular
It can have no solution (or) infinitely many solutions.
Option B is true.
⇾ x ≠ 0 such that Fx = 0 is True because F is singular matrix (“stated by singular matrix rules). Option C is true.
⇾ F can two identical columns and rows.
Option D is false.
Fu = Fv
Fu  Fv = 0
F(u  v) = 0
Given u ≠ v
F = 0 (i.e., Singular matrix, so determinant is zero)
Option A is true.
⇾ Fx = b; where F is singular
It can have no solution (or) infinitely many solutions.
Option B is true.
⇾ x ≠ 0 such that Fx = 0 is True because F is singular matrix (“stated by singular matrix rules). Option C is true.
⇾ F can two identical columns and rows.
Option D is false.
Question 24 
Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A⊆N and B⊆N, how many of the n! permutations π from N to N satisfy min(π(A)) = min(π(B)), where min(S) is the smallest integer in the set of integers S, and π(S) is the set of integers obtained by applying permutation π to each element of S?
(nA ∪ B) A B  
(A^{2}+B^{2})n^{2}
 
n!(A∩B/A∪B)  
Question 24 Explanation:
Given a set of elements N = {1, 2, 3, ...N}
Two arbitrary subsets A⊆N and B⊆N.
Out of n! permutations π from N to N, to satisfy
min(π(A)) = min (π(B))
*) π(S) is the set of integers obtained by applying permutation π to each element of S.
If min(π(A)) =min (π(B)), say y = π(x) is the common minimum.
Since the permutation π is a 1to1 mapping of N,
x ∈ A∩B
∴ A∩B cannot be empty.
⇒ y = π(x)
= π(A∩B) is the minimum of π(A∪B) is the minimum of π(A) and π(B) are to be same.
You can think like
*) If the minimum of π(A) and π(B) are same [min π(A)] = min [π(B)]
then min(π(A∩B)) = min(π(A∪B))
∴ Total number is given by n! A∩B/A∪B
*) Finally
Considering all possible permutations, the fraction of them that meet this condition π(A∩B) / π(A∪B)
[The probability of single permutation].
Ex: N = {1, 2, 3, 4} A = {1, 3} B = {1, 2, 4}
Since π is one to one mapping
π(A∩B) = A∩B
∴ π(A) = {1, 2}
π(B) = {1, 4, 3}
π(A∩B) = {1}
π(A∪B) = {1, 2, 3, 4}
4! × 1/4 = 6
Two arbitrary subsets A⊆N and B⊆N.
Out of n! permutations π from N to N, to satisfy
min(π(A)) = min (π(B))
*) π(S) is the set of integers obtained by applying permutation π to each element of S.
If min(π(A)) =min (π(B)), say y = π(x) is the common minimum.
Since the permutation π is a 1to1 mapping of N,
x ∈ A∩B
∴ A∩B cannot be empty.
⇒ y = π(x)
= π(A∩B) is the minimum of π(A∪B) is the minimum of π(A) and π(B) are to be same.
You can think like
*) If the minimum of π(A) and π(B) are same [min π(A)] = min [π(B)]
then min(π(A∩B)) = min(π(A∪B))
∴ Total number is given by n! A∩B/A∪B
*) Finally
Considering all possible permutations, the fraction of them that meet this condition π(A∩B) / π(A∪B)
[The probability of single permutation].
Ex: N = {1, 2, 3, 4} A = {1, 3} B = {1, 2, 4}
Since π is one to one mapping
π(A∩B) = A∩B
∴ π(A) = {1, 2}
π(B) = {1, 4, 3}
π(A∩B) = {1}
π(A∪B) = {1, 2, 3, 4}
4! × 1/4 = 6
Question 25 
3m  
3n  
2m+1  
2n+1 
Question 25 Explanation:
No. of subsets of size 3 is = ^{m}C_{3}
n = ^{m}C_{3}
Which subsets contains element i then size is
= ^{(m1)}C_{2}
Because 1 element is already known
n = ^{m}C_{3}
Which subsets contains element i then size is
= ^{(m1)}C_{2}
Because 1 element is already known
Question 26 
∀x [(tiger(x) ∧ lion(x)) → {(hungry(x) ∨ threatened(x))
→ attacks(x)}]  
∀x [(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x))
∧ attacks(x)}]  
∀x [(tiger(x) ∨ lion(x)) → {(attacks(x) → (hungry (x)) ∨ threatened (x))}]  
∀x [(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]

Question 26 Explanation:
Tigers and lions attack if they are hungry (or) threatened.
Here we have two cases.
i) If Tiger is hungry (or) threaten that will attack.
ii) If Lion is hungry (or) threaten that will attack.
If Tiger is hungry (or) threaten then both lion and tiger will not attack only Tiger will attack and viceversa.
Then answer is
∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]
Note: Don’t confuse with the statement Tiger and Lion.
Here we have two cases.
i) If Tiger is hungry (or) threaten that will attack.
ii) If Lion is hungry (or) threaten that will attack.
If Tiger is hungry (or) threaten then both lion and tiger will not attack only Tiger will attack and viceversa.
Then answer is
∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]
Note: Don’t confuse with the statement Tiger and Lion.
Question 27 
P1 is a tautology, but not P2
 
P2 is a tautology, but not P1
 
P1 and P2 are both tautologies  
Both P1 and P2 are not tautologies

Question 27 Explanation:
It’s better to draw truth table such that
Both P1 and P2 are not Tautologies.
Both P1 and P2 are not Tautologies.
Question 28 
(~A B)  
~(A ~B)  
~(~A ~B)  
~(~ A B) 
Question 28 Explanation:
Question 29 
If s is a string over (0 + 1)* then let n_{0}(s) denote the number of 0’s in s and n_{1}(s) the number of 1’s in s. Which one of the following languages is not regular?
L = {s ∈ (0+1)*  n_{0}(s) is a 3digit prime}  
L = {s ∈ (0+1)*  for every prefix s' of s,n_{0}(s')  n_{1}(s') ≤ 2}  
L = {s ∈ (0+1)* n_{0}(s)  n_{1}(s) ≤ 4}
 
L = {s ∈ (0+1)*  n_{0}(s) mod 7 = n_{1}(s) mod 5 = 0}

Question 29 Explanation:
Since 3digit prime numbers are finite so language in option A is finite, hence it is regular.
Option B: The DFA contains 6 states
State1: n_{0}(s')  n_{1}(s') = 0
State2: n_{0}(s')  n_{1}(s') = 1
State3: n_{0}(s')  n_{1}(s') = 2
State4: n_{0}(s')  n_{1}(s') = 1
State5: n_{0}(s')  n_{1}(s') = 2
State6: Dead state (trap state)
Hence it is regular.
Option D: Product automata concept is used to construct the DFA.
mod 7 has remainders {0,1,2,3,4,5,6} and mod 5 remainders {0,1,2,3,4}
So product automata will have 35 states.
But option C has infinite comparisons between number of 0’s and 1’s.
For ex: n_{0}(s) = 5 and n_{1}(s) = 1 then n_{0}(s)  n_{1}(s) = 4 and if n_{0}(s) = 15 and n_{1}(s) = 11 then n_{0}(s)  n_{1}(s) = 4.
Hence this is CFL.
Option B: The DFA contains 6 states
State1: n_{0}(s')  n_{1}(s') = 0
State2: n_{0}(s')  n_{1}(s') = 1
State3: n_{0}(s')  n_{1}(s') = 2
State4: n_{0}(s')  n_{1}(s') = 1
State5: n_{0}(s')  n_{1}(s') = 2
State6: Dead state (trap state)
Hence it is regular.
Option D: Product automata concept is used to construct the DFA.
mod 7 has remainders {0,1,2,3,4,5,6} and mod 5 remainders {0,1,2,3,4}
So product automata will have 35 states.
But option C has infinite comparisons between number of 0’s and 1’s.
For ex: n_{0}(s) = 5 and n_{1}(s) = 1 then n_{0}(s)  n_{1}(s) = 4 and if n_{0}(s) = 15 and n_{1}(s) = 11 then n_{0}(s)  n_{1}(s) = 4.
Hence this is CFL.
Question 30 
L is recursively enumerable, but not recursive  
L is recursive, but not contextfree
 
L is contextfree, but not regular  
L is regular

Question 30 Explanation:
Let L_{1} = {s ∈ (0 + 1)*  d(s) mod5 = 2}, we can construct the DFA for this which will have 5 states (remainders 0,1,2,3,4)
L_{2} = {s ∈ (0 + 1)*  d(s) mod7 = 4}, we can construct the DFA for this which will have 7 states (remainders 0,1,2,3,4,5,6)
Since L_{1} and L_{2} have DFAs, hence they are regular. So the resulting Language.
L = L_{1} ∩ L_{2} (compliment) must be regular (by closure properties, INTERSECTION of two regular languages is a regular language).
L_{2} = {s ∈ (0 + 1)*  d(s) mod7 = 4}, we can construct the DFA for this which will have 7 states (remainders 0,1,2,3,4,5,6)
Since L_{1} and L_{2} have DFAs, hence they are regular. So the resulting Language.
L = L_{1} ∩ L_{2} (compliment) must be regular (by closure properties, INTERSECTION of two regular languages is a regular language).
Question 31 
Let SHAM_{3} be the problem of finding a Hamiltonian cycle in a graph G = (V,E) with V divisible by 3 and DHAM_{3} be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
Both DHAM_{3} and SHAM_{3} are NPhard  
SHAM_{3} is NPhard, but DHAM_{3} is not
 
DHAM_{3} is NPhard, but SHAM_{3} is not  
Neither DHAM_{3} nor SHAM_{3} is NPhard

Question 31 Explanation:
Whether to finding a hamiltonian cycles exist (or) not is a NP Hard problem. So both DHAM_{3} and SHAM_{3} are NPhard.
Question 32 
I only  
I and III only
 
II and III only
 
I, II and III

Question 32 Explanation:
Is ambiguous, as it has two parse tree for the string “abbaba”
G doesn’t product all strings of equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:
G doesn’t product all strings of equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:
Question 33 
Let L_{1} be a regular language, L_{2} be a deterministic contextfree language and L_{3} a recursively enumerable, but not recursive, language. Which one of the following statements is false?
L_{1} ∩ L_{2} is a deterministic CFL  
L_{3} ∩ L_{1} is recursive  
L_{1} ∪ L_{2} is context free  
L_{1} ∩ L_{2} ∩ L_{3} is recursively enumerable 
Question 33 Explanation:
Option A is true, as by closure property (R is a regular language and L is any language)
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L_{1} ∩ L_{2} is a deterministic CFL.
Option B is false, as L_{3} is recursive enumerable but not recursive, so intersection with L_{1} must be recursive enumerable, but may or may not be recursive.
Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L_{1} ∪ L_{2} is deterministic context free, hence it is also context free.
Option D is true, as L_{1} ∩ L_{2} is DCFL and DCFL ∩ L_{3} is equivalent to DCFL ∩ Recursive enumerable.
As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L_{1} ∩ L_{2} is a deterministic CFL.
Option B is false, as L_{3} is recursive enumerable but not recursive, so intersection with L_{1} must be recursive enumerable, but may or may not be recursive.
Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L_{1} ∪ L_{2} is deterministic context free, hence it is also context free.
Option D is true, as L_{1} ∩ L_{2} is DCFL and DCFL ∩ L_{3} is equivalent to DCFL ∩ Recursive enumerable.
As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.
Question 34 
Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this language is:
3  
5  
8  
9 
Question 34 Explanation:
L = (111 + 11111)* generates the strings {ϵ, 111, 11111, 111111, 11111111, …….}
i.e. it generates any string which can be obtained by repetition of three and five 1’s (means length 3, 6, 8, 9, 10, 11, …}
The DFA for the L = (111 + 11111)* is given below.
i.e. it generates any string which can be obtained by repetition of three and five 1’s (means length 3, 6, 8, 9, 10, 11, …}
The DFA for the L = (111 + 11111)* is given below.
Question 35 
Question 35 Explanation:
f = yx + y’ (zy’+z’x)
= xy + zy’ + y’z’x
= x(y+y’z’) + zy’
= x(y+z’) + y’z
= xy + xz’ + y’z
= xy + zy’ + y’z’x
= x(y+y’z’) + zy’
= x(y+z’) + y’z
= xy + xz’ + y’z
Question 36 
Given two three bit numbers a_{2}a_{1}a_{0} and b_{2}b_{1}b_{0} and c, the carry in, the function that represents the carry generate function when these two numbers are added is:
Question 36 Explanation:
Initial Carry c is not included in any option. Hence c=0.
Carry c_{1} = a_{0}b_{0}
Carry c_{2} = a_{2}b_{2} + c_{1}(a_{2} ⊕ b_{2} )
= a_{1}b_{1} +c_{1} (a_{1} b’_{1}+ a’_{1} b_{1} )
= a_{1}b_{1} +c_{1} a_{1} b’_{1}+ c_{1} a’_{1} b_{1}
= (a_{1}b_{1} + c_{1}a_{1} b’_{1})+ (c_{1} a’_{1} b_{1} + a_{1}b_{1} )
= a_{1}(b_{1}+c_{1}) +b_{1} (c_{1} + a_{1})
= a_{1}b_{1}+b_{1}c_{1}+a_{1}c_{1}
Carry c_{3} = a_{2}b_{2} + c_{2}(a_{2} ⊕ b_{2})
= a_{2}b_{2} + c_{2}(a’_{2}b_{2} + a_{2}b’_{2} )
= a_{2}b_{2} + b_{2}c_{2} + a_{2}c_{2}
= a_{2}b_{2}+a_{2}a_{1}b_{1}+a_{2}a_{1}a_{0}b_{0}+a_{2}a_{0}b_{1}b_{0}+a_{1}b_{2}b_{1}+a_{1}a_{0}b_{2}b_{0}+a_{0}b_{2}b_{1}b_{0}
Carry c_{1} = a_{0}b_{0}
Carry c_{2} = a_{2}b_{2} + c_{1}(a_{2} ⊕ b_{2} )
= a_{1}b_{1} +c_{1} (a_{1} b’_{1}+ a’_{1} b_{1} )
= a_{1}b_{1} +c_{1} a_{1} b’_{1}+ c_{1} a’_{1} b_{1}
= (a_{1}b_{1} + c_{1}a_{1} b’_{1})+ (c_{1} a’_{1} b_{1} + a_{1}b_{1} )
= a_{1}(b_{1}+c_{1}) +b_{1} (c_{1} + a_{1})
= a_{1}b_{1}+b_{1}c_{1}+a_{1}c_{1}
Carry c_{3} = a_{2}b_{2} + c_{2}(a_{2} ⊕ b_{2})
= a_{2}b_{2} + c_{2}(a’_{2}b_{2} + a_{2}b’_{2} )
= a_{2}b_{2} + b_{2}c_{2} + a_{2}c_{2}
= a_{2}b_{2}+a_{2}a_{1}b_{1}+a_{2}a_{1}a_{0}b_{0}+a_{2}a_{0}b_{1}b_{0}+a_{1}b_{2}b_{1}+a_{1}a_{0}b_{2}b_{0}+a_{0}b_{2}b_{1}b_{0}
Question 37 
000  
001  
010  
101 
Question 37 Explanation:
q_{0N} = Data, q_{1N} = q_{0}q_{22N} = q_{1}
Question 38 
Consider a Boolean function f (w, x, y, z). Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors i_{1} = 〈w_{1}, x_{1}, y_{1}, z_{1}〉 and i_{2} = 〈w_{2}, x_{2}, y_{2}, z_{2}〉, we would like the function to remain true as the input changes from vectors i_{1} to i_{2} (i_{1} and i_{2} differ in exactly one bit position), without becoming false momentarily. Let f(w, x, y, z) = ∑(5, 7, 11, 12, 13, 15). Which of the following cube covers of f will ensure that the required property is satisfied?
Question 38 Explanation:
Static hazard is the situation where, when one input variable changes, the output changes momentarily before stabilizing to the correct value. The most commonly used method to eliminate static hazards is to add redundant logic (consensus terms in the logic expression).
f = X_{1} * X_{2} + X_{1}' * X_{3}
If (X_{1},X_{2},X_{3}) = (1,1,1) then f=1 because X_{1} * X_{2} =1 X_{1}' * X_{3} = 0.
Let the input is changed from 111 to 011 , then f = 1 because X_{1} * X_{2} = 0 X_{1}' * X_{3} =1.
The output f will be momentarily 0 if AND gate X_{1} * X_{2} is faster than the AND gate X_{1}' * X_{}3.
This Hazard can be avoided by adding the term X_{2} * X_{3} (because X_{1} is in true form in first term and in complement form in the second term . So pick the fixed terms X_{2} and X_{3} from both terms) to f i.e f = X_{1} * X_{2} + X_{1}' * X_{3} + X_{2} * X_{3}
Option D is equivalent to f(w, x, y, z) = ∑(5,7,11,12,13,15)
f = X_{1} * X_{2} + X_{1}' * X_{3}
If (X_{1},X_{2},X_{3}) = (1,1,1) then f=1 because X_{1} * X_{2} =1 X_{1}' * X_{3} = 0.
Let the input is changed from 111 to 011 , then f = 1 because X_{1} * X_{2} = 0 X_{1}' * X_{3} =1.
The output f will be momentarily 0 if AND gate X_{1} * X_{2} is faster than the AND gate X_{1}' * X_{}3.
This Hazard can be avoided by adding the term X_{2} * X_{3} (because X_{1} is in true form in first term and in complement form in the second term . So pick the fixed terms X_{2} and X_{3} from both terms) to f i.e f = X_{1} * X_{2} + X_{1}' * X_{3} + X_{2} * X_{3}
Option D is equivalent to f(w, x, y, z) = ∑(5,7,11,12,13,15)
Question 39 
We consider the addition of two 2’s complement numbers b_{n1}b_{n2}...b_{0} and a_{n1}a_{n2}…a_{0}. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by c_{n1}c_{n2}c_{0} and the carryout by c_{out}. Which one of the following options correctly identifies the overflow condition?
Question 39 Explanation:
There is an overflow if
1. The sign bits are same i.e MSB bits are same.
2. Carry_in ≠ Carry_out.
In option B, the MSB are equal.
1. The sign bits are same i.e MSB bits are same.
2. Carry_in ≠ Carry_out.
In option B, the MSB are equal.
Question 40 
Consider numbers represented in 4bit gray code. Let h_{3}h_{2}h_{1}h_{0} be the gray code representation of a number n and let g_{3}g_{2}g_{1}g_{0} be the gray code of (n+1) (modulo 16) value of the number. Which one of the following functions is correct?
g_{0}(h_{3}h_{2}h_{1}h_{0}) = Σ(1,2,3,6,10,13,14,15)  
g_{1}(h_{3}h_{2}h_{1}h_{0}) = Σ(4,9,10,11,12,13,14,15)  
g_{2}(h_{3}h_{2}h_{1}h_{0}) = Σ(2,4,5,6,7,12,13,15)  
g_{3}(h_{3}h_{2}h_{1}h_{0}) = Σ(0,1,6,7,10,11,12,13)

Question 40 Explanation:
g_{2}(h_{3}h_{2}h_{1}h_{0}) = Σ(2,4,5,6,7,12,13,15)
Question 41 
92 ns  
104 ns  
172 ns  
184 ns 
Question 41 Explanation:
Cache with block size = 64 bytes
Latency = 80 ns
k = 24
No. of banks are accessed in parallel , then it takes k/2 ns = 24/2 = 12ns
Decoding time = 12ns
Size of each bank C = 2 bytes
Each Bank memory is 2 bytes, and there is 24 banks are there, in one iteration they may get 2*24 = 48 bytes
And getting 64 bytes requires 2 iteration.
T = decoding time + latency = 12+80 = 92
For 2 iterations = 92×2 = 184ns
Latency = 80 ns
k = 24
No. of banks are accessed in parallel , then it takes k/2 ns = 24/2 = 12ns
Decoding time = 12ns
Size of each bank C = 2 bytes
Each Bank memory is 2 bytes, and there is 24 banks are there, in one iteration they may get 2*24 = 48 bytes
And getting 64 bytes requires 2 iteration.
T = decoding time + latency = 12+80 = 92
For 2 iterations = 92×2 = 184ns
Question 42 
A CPU has a fivestage pipeline and runs at 1 GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the condition in the third stage of the pipeline. The processor stops fetching new instructions following a conditional branch until the branch outcome is known. A program executes 10^{9} instructions out of which 20% are conditional branches. If each instruction takes one cycle to complete on average, the total execution time of the program is:
1.0 second  
1.2 seconds  
1.4 seconds  
1.6 seconds 
Question 42 Explanation:
No. of total instructions = 10^{9}
20% are condition branches out of 10^{9}
⇒ 20/100 × 10^{9}
⇒ 2 × 10^{8}
In third stage of pipeline it consists of 2 stage cycles.
Total cycle penalty = 2 × 2 × 10^{8} = 4 × 10^{8}
Clock speed = 1 GHz
Each Instruction takes 1 cycle i.e., 10^{9} instructions.
Total execution time of a program is
= (10^{9} / 10^{9}) +((4× 10^{8}) / 10^{9}) = 1+0.4 = 1.4seconds
20% are condition branches out of 10^{9}
⇒ 20/100 × 10^{9}
⇒ 2 × 10^{8}
In third stage of pipeline it consists of 2 stage cycles.
Total cycle penalty = 2 × 2 × 10^{8} = 4 × 10^{8}
Clock speed = 1 GHz
Each Instruction takes 1 cycle i.e., 10^{9} instructions.
Total execution time of a program is
= (10^{9} / 10^{9}) +((4× 10^{8}) / 10^{9}) = 1+0.4 = 1.4seconds
Question 43 
mask ← 0×1 □ pos  
mask ← 0×ffffffff □ pos  
mask ← pos
 
mask ← 0×f

Question 43 Explanation:
Using the following operation "temp→reg & mask" we are checking whether bit at position pos in register reg is 1 or not. For that mask should have 1 only in position pos. In all the other positions mask have 0s.
So for mask to have 1 only in position pos and 0s in all the other positions, we can get it by doing left shift on 1, pos number of times.
Out of the given options, in option A this left shift operation on 1 is performed pos number of times. Hence option A is the answer.
So for mask to have 1 only in position pos and 0s in all the other positions, we can get it by doing left shift on 1, pos number of times.
Out of the given options, in option A this left shift operation on 1 is performed pos number of times. Hence option A is the answer.
Question 44 
Station A uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip delay between A and B is 80 milliseconds and the bottleneck bandwidth on the path between A and B is 128 kbps. What is the optimal window size that A should use?
20  
40  
160  
320 
Question 44 Explanation:
T_{t} = L / B = 32 bytes/ 128 kbps = 32*8/128 ms = 2 ms
Round trip delay = 2 * Tp = 80 ms (given)
Optimal window size is = (T_{t} + 2*T_{p}) / T_{t} = 82 / 2 = 41
Option is not given, closest option is 40.
Round trip delay = 2 * Tp = 80 ms (given)
Optimal window size is = (T_{t} + 2*T_{p}) / T_{t} = 82 / 2 = 41
Option is not given, closest option is 40.
Question 45 
Two computers C1 and C2 are configured as follows. C1 has IP address 203.197.2.53 and netmask 255.255.128.0. C2 has IP address 203.197.75.201 and netmask 255.255.192.0. Which one of the following statements is true?
C1 and C2 both assume they are on the same network
 
C2 assumes C1 is on same network, but C1 assumes C2 is on a different network  
C1 assumes C2 is on same network, but C2 assumes C1 is on a different network  
C1 and C2 both assume they are on different networks

Question 45 Explanation:
From C1 side,
Subnet mask for C1 is 255.255.128.0.
So it finds the Network ID as,
C1 → 203.197.2.53 AND 255.255.128.0 = 203.197.0.0
C2 → 203.197.75.201 AND 255.255.128.0 = 203.197.0.0
Both same.
From C2 side,
Subnet mask for C2 is 255.255.192.0.
So it finds the network ID as,
C1 → 203.197.2.53 AND 255.255.192.0 = 203.197.0.0
C2 → 203.197.75.201 AND 255.255.192.0 = 203.197.64.0
Both different.
Hence, option 'C' is correct.
Subnet mask for C1 is 255.255.128.0.
So it finds the Network ID as,
C1 → 203.197.2.53 AND 255.255.128.0 = 203.197.0.0
C2 → 203.197.75.201 AND 255.255.128.0 = 203.197.0.0
Both same.
From C2 side,
Subnet mask for C2 is 255.255.192.0.
So it finds the network ID as,
C1 → 203.197.2.53 AND 255.255.192.0 = 203.197.0.0
C2 → 203.197.75.201 AND 255.255.192.0 = 203.197.64.0
Both different.
Hence, option 'C' is correct.
Question 46 
Station A needs to send a message consisting of 9 packets to Station B using a sliding window (window size 3) and gobackn error control strategy. All packets are ready and immediately available for transmission. If every 5^{th} packet that A transmits gets lost (but no acks from B ever get lost), then what is the number of packets that A will transmit for sending the message to B?
12  
14  
16  
18 
Question 46 Explanation:
Window size is 3, so maximum 3 packets can be remained unacknowledged. In go back ‘n’ if acknowledge for a packet is not received then packets after that packet is also retransmitted.
Frame sequence for 9 frame is shown below. Frame with bold sequence number gets lost.
1 2 3 4 [5 6 7] 5 6 [7 8 9] 7 8 9 9 = 16
Frame sequence for 9 frame is shown below. Frame with bold sequence number gets lost.
1 2 3 4 [5 6 7] 5 6 [7 8 9] 7 8 9 9 = 16
Question 47 
(a—b),(d—f),(b—f),(d—c),(d—e)
 
(a—b),(d—f),(d—c),(b—f),(d—e)  
(d—f),(a—b),(d—c),(b—f),(d—e)
 
(d—f),(a—b),(b—f),(d—e),(d—c)

Question 47 Explanation:
To find Minimum Spanning Tree(MST) using Kruskal’s algorithm we have to follow standard procedure is
1. It follows like forest structure (Means we are disconnecting all the edges connected to vertices).
2. Sort edge weights in Ascending order.
3. Always select the minimum edge weight first according to Spanning Tree rules.
Note: The edge de cannot be considered before dc.
1. It follows like forest structure (Means we are disconnecting all the edges connected to vertices).
2. Sort edge weights in Ascending order.
3. Always select the minimum edge weight first according to Spanning Tree rules.
Note: The edge de cannot be considered before dc.
Question 48 
Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?
There must exist a vertex w adjacent to both u and v in G
 
There must exist a vertex w whose removal disconnects u and v in G  
There must exist a cycle in G containing u and v
 
There must exist a cycle in G containing u and all its neighbours in G 
Question 48 Explanation:
Very difficult assume a graphs here. So, As per the GATE key they given Option D is correct answer.
Question 49 
n+m ≤ x < 2n and 2m ≤ y ≤ n+m
 
n+m ≤ x< 2n and 2m ≤y ≤ 2n  
2m ≤ x< 2n and 2m ≤ y ≤ n+m
 
2m ≤ x < 2n and 2m ≤ y ≤ 2n 
Question 49 Explanation:
Let's first consider for push, i.e., x.
Best case:
First push m elements in S1 then pop m elements from S1 and push them in S2 and then pop all m elements from S2. Now push remaining (nm) elements to S1.
So total push operation
= m + m + (nm)
= n+m
Worst Case:
First push all n elements in S1. Then pop n elements from S1 and push them into S2. Now pop m elements from S2.
So total push operation
= n+n
= 2n
Now lets consider for pop operation, i.e., y.
For best case:
First push m elements in S1, then pop m elements and push them in S2. Now pop that m elements from S2. Now push remaining (nm) elements in S1.
So total pop operation
= m+m
= 2m
For worst case:
First push n elements in S1, then pop them from S1 and push them into S2. Now pop m elements fro m S2.
So total pop operation
= n+m
Therefore, option A is correct answer.
Best case:
First push m elements in S1 then pop m elements from S1 and push them in S2 and then pop all m elements from S2. Now push remaining (nm) elements to S1.
So total push operation
= m + m + (nm)
= n+m
Worst Case:
First push all n elements in S1. Then pop n elements from S1 and push them into S2. Now pop m elements from S2.
So total push operation
= n+n
= 2n
Now lets consider for pop operation, i.e., y.
For best case:
First push m elements in S1, then pop m elements and push them in S2. Now pop that m elements from S2. Now push remaining (nm) elements in S1.
So total pop operation
= m+m
= 2m
For worst case:
First push n elements in S1, then pop them from S1 and push them into S2. Now pop m elements fro m S2.
So total pop operation
= n+m
Therefore, option A is correct answer.
Question 50 
(X ∪ Y)
 
(X ∩ Y)  
(XY) ∩ (YX)
 
(XY) ∪ (YX) 
Question 50 Explanation:
X[i] ∧ ~Y[i] can be written as X  Y.
~X[i] ∧ Y[i] can be written as Y  X.
'∨' can be written as Union.
∴(XY) Union (YX)
~X[i] ∧ Y[i] can be written as Y  X.
'∨' can be written as Union.
∴(XY) Union (YX)
Question 51 
T(n) = θ(loglogn)
 
T(n) = θ(logn)
 
T(n) = θ(√n)  
T(n) = θ(n) 
Question 51 Explanation:
T(n) = 2T(√n)+1
Let n =2^{m}
T(2^{m}) = 2T(2^{m/2}) + 1 (1)
Let T(2^{m}) = S(m)
Then equation (1) becomes,
S(m) = 2S(m/2) + 1
So now lets apply Master's theorem,
a=2, b=2, k=0
Since, a>b^{k}, so Case 1 applied here
But m = log n
So finally the answer is,
O(log n)
Let n =2^{m}
T(2^{m}) = 2T(2^{m/2}) + 1 (1)
Let T(2^{m}) = S(m)
Then equation (1) becomes,
S(m) = 2S(m/2) + 1
So now lets apply Master's theorem,
a=2, b=2, k=0
Since, a>b^{k}, so Case 1 applied here
But m = log n
So finally the answer is,
O(log n)
Question 52 
The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?
θ(n)
 
θ(nlog n)
 
θ(n^{2})
 
θ(n^{3})

Question 52 Explanation:
If we choose pivot element element as median then the recurrence relation will be
T(n) = 2T(n/2) +O(n)
The above recurrence in the form of masters theorem: a=2, b=2, k=1, p=0. Since, a=b^{k}, so Case2 is applied
and also p > 1, so
T(n) = 2T(n/2) +O(n)
The above recurrence in the form of masters theorem: a=2, b=2, k=1, p=0. Since, a=b^{k}, so Case2 is applied
and also p > 1, so
Question 53 
only (i)  
only (ii)
 
either (i) or (ii) but not both  
neither (i) nor (ii) 
Question 53 Explanation:
The while loop adds element from 'a' and 'b' to 'c' and terminates when either of them exhausts. So, when loop terminates either i=n or j=m.
Suppose i=n. This would mean all elements from array 'a' are added to 'c' and k must be incremented by n. 'c' would also contain j elements from array 'b'.
So, number of elements in 'c' would be n+j and hence k=n+j.
Similarly, when j=m, k=m+i.
Hence, option (D) is correct.
Suppose i=n. This would mean all elements from array 'a' are added to 'c' and k must be incremented by n. 'c' would also contain j elements from array 'b'.
So, number of elements in 'c' would be n+j and hence k=n+j.
Similarly, when j=m, k=m+i.
Hence, option (D) is correct.
Question 54 
Takes O(3^{n}) and Ω(2^{n}) time if hashing is permitted
 
Takes O(n^{3}) and Ω(n^{2.5}) time in the key comparison model  
Takes θ(n) time and space  
Takes O(√n) time only if the sum of the 2n elements is an even number 
Question 54 Explanation:
As per the above question, the algorithms follows in
1. Since there are total n elements, maximum sum is n for both arrays.
2. Difference between two sums varies from n to n. So there are total 2n + 1 possible values of difference.
3. If differences between prefix sums of two arrays become same at two points, then subarrays between these two points have same sum.
1. Since there are total n elements, maximum sum is n for both arrays.
2. Difference between two sums varies from n to n. So there are total 2n + 1 possible values of difference.
3. If differences between prefix sums of two arrays become same at two points, then subarrays between these two points have same sum.
Question 55 
S1 is false and S2 is false
 
S1 is false and S2 is true
 
S1 is true and S2 is false
 
S1 is true and S2 is true

Question 55 Explanation:
We cannot compare the program on the basis of runtime with respect to any inputs.
So, given statement is wrong.
S1: Let us assume an array = {1,2,3,4,5} and i=0.
Let j = i+2 = 0+2 = 2
For the respective example work1 and work2 results 1 and 0, so S1 statement is False.
So, given statement is wrong.
S1: Let us assume an array = {1,2,3,4,5} and i=0.
Let j = i+2 = 0+2 = 2
For the respective example work1 and work2 results 1 and 0, so S1 statement is False.
Question 56 
S1 and S2
 
S1 and S4
 
S3  
S1 and S5

Question 56 Explanation:
Swap operation perform between the ia and temporary nameless cell, therefore the value of ib is remains unchanged.
Swap (8, 13)
⇒ ia will returns value with 13.
⇒ ib is unchanged, because here we using pass by reference value.
➝ Temporary nameless is initialized to 13.
➝ There is No runtime error.
Swap (8, 13)
⇒ ia will returns value with 13.
⇒ ib is unchanged, because here we using pass by reference value.
➝ Temporary nameless is initialized to 13.
➝ There is No runtime error.
Question 57 
S1  
S2 and S3  
S2 and S4
 
S2 and S5

Question 57 Explanation:
S2:
We may get the segmentation fault if the pointer values are constant (i.e., px or py) (or) (px or py) are points to a memory location is invalid.
S4:
Swap procedure can be implemented correctly but not for all input pointers because arithmetic overflow may occur based on input values.
We may get the segmentation fault if the pointer values are constant (i.e., px or py) (or) (px or py) are points to a memory location is invalid.
S4:
Swap procedure can be implemented correctly but not for all input pointers because arithmetic overflow may occur based on input values.
Question 58 
{S → FR} and {R → ε}
 
{S → FR} and { }  
{S → FR} and {R → *S}  
{F → id} and {R → ε} 
Question 58 Explanation:
Predictive parsing table for the mentioned grammar:
The representation M[X,Y] means X represents Variable (rows) and Y represents terminals (columns).
The productions are filled in parsing table by the below mentioned rules:
For every production P → α, we have:
Rule 1: If P → α is a production then add this production for each terminal “t” which is in FIRST of [α] i.e., ADD P → α to M[P, a]
Rule 2: If “ϵ” belongs to FIRST of [P] then add P → α to M[P, b] where “b” represents terminals FOLLOW[P].
By the above rules, we can see that production S → FR will go M[S, a] where “a” is FIRST [FR] which is equal to FIRST[F] = id, So S → FR will go in M[S,id].
Since in the production R→ϵ , FIRST[ϵ] = ϵ, hence the production will go in M[R, b] where “b” represents terminals FOLLOW[R] and FOLLOW[R] = $, so production R→ϵ will go in M[R,$]
The representation M[X,Y] means X represents Variable (rows) and Y represents terminals (columns).
The productions are filled in parsing table by the below mentioned rules:
For every production P → α, we have:
Rule 1: If P → α is a production then add this production for each terminal “t” which is in FIRST of [α] i.e., ADD P → α to M[P, a]
Rule 2: If “ϵ” belongs to FIRST of [P] then add P → α to M[P, b] where “b” represents terminals FOLLOW[P].
By the above rules, we can see that production S → FR will go M[S, a] where “a” is FIRST [FR] which is equal to FIRST[F] = id, So S → FR will go in M[S,id].
Since in the production R→ϵ , FIRST[ϵ] = ϵ, hence the production will go in M[R, b] where “b” represents terminals FOLLOW[R] and FOLLOW[R] = $, so production R→ϵ will go in M[R,$]
Question 59 
2 * 3 + 4
 
2 * +3 4
 
2 3 * 4 +
 
2 3 4+*

Question 59 Explanation:
Now perform post order evaluation, you will get output as,
2 3 4 + *
Question 60 
The code contains loop invariant computation
 
There is scope of common subexpression elimination in this code  
There is scope of strength reduction in this code
 
There is scope of dead code elimination in this code

Question 60 Explanation:
→ 4*j is a common subexpression. So there is a scope of elimination. So B is correct.
→ 5*i can be moved out of inner loop. So can be i%2, here loopinvarient computation can be done, so option A is correct.
→ 4*i, 5*j can also be replaced so there is a scope of strength reduction. So C is true.
→ But there is no dead code to eliminate, we can replace the variable representation only.
→ 5*i can be moved out of inner loop. So can be i%2, here loopinvarient computation can be done, so option A is correct.
→ 4*i, 5*j can also be replaced so there is a scope of strength reduction. So C is true.
→ But there is no dead code to eliminate, we can replace the variable representation only.
Question 61 
The implementation may not work if context switching is disabled in P  
Instead of using fetchandset, a pair of normal load/store can be used  
The implementation of V is wrong
 
The code does not implement a binary semaphore 
Question 61 Explanation:
A) This is correct because implementation might not work if context switching is disabled in P, then process which is currently blocked may never give control to the process which might eventually execute v. So context switching is must.
B) If we use normal load and store instead of Fetch and Set, then there can be chance that more than one process sees S.value as 0 and then mutual exclusion will not be satisfied. So wrong.
C) Here we are setting S→value to 0, which is correct. This option thats why wrong.
D) Only one process can be in critical section at any time. So this option is wrong.
B) If we use normal load and store instead of Fetch and Set, then there can be chance that more than one process sees S.value as 0 and then mutual exclusion will not be satisfied. So wrong.
C) Here we are setting S→value to 0, which is correct. This option thats why wrong.
D) Only one process can be in critical section at any time. So this option is wrong.
Question 62 
A CPU generates 32bit virtual addresses. The page size is 4 KB. The processor has a translation lookaside buffer (TLB) which can hold a total of 128 page table entries and is 4way set associative. The minimum size of the TLB tag is:
11 bits
 
13 bits  
15 bits
 
20 bits 
Question 62 Explanation:
Page size = 4 KB = 4 × 2^{10} Bytes = 2^{12} Bytes
Virtual Address = 32 bit
No. of bits needed to address the page frame = 32  12 = 20
TLB can hold 128 page table entries with 4way set associative
⇒ 128/4=32=2^{5}
→ 5 bits are needed to address a set.
→ The size of TLB tag = 20  5 = 15 bits
Virtual Address = 32 bit
No. of bits needed to address the page frame = 32  12 = 20
TLB can hold 128 page table entries with 4way set associative
⇒ 128/4=32=2^{5}
→ 5 bits are needed to address a set.
→ The size of TLB tag = 20  5 = 15 bits
Question 63 
A computer system supports 32bit virtual addresses as well as 32bit physical addresses. Since the virtual address space is of the same size as the physical address space, the operating system designers decide to get rid of the virtual memory entirely. Which one of the following is true?
Efficient implementation of multiuser support is no longer possible
 
The processor cache organization can be made more efficient now
 
Hardware support for memory management is no longer needed  
CPU scheduling can be made more efficient now 
Question 63 Explanation:
→ When designer decides to get rid of virtual memory entirely then hardware support is no longer needed.
→ Because special hardware support needed only for virtual memory.
→ Because special hardware support needed only for virtual memory.
Question 64 
Consider three processes (process id 0, 1, 2 respectively) with compute time bursts 2, 4 and 8 time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. The average turnaround time is:
13 units
 
14 units
 
15 units
 
16 units

Question 64 Explanation:
Algorithm: LRTF (Longest Remaining Time First)
Avg TAT = 12+13+14/3 = 39/3 = 13 units
Avg TAT = 12+13+14/3 = 39/3 = 13 units
Question 65 
Consider three processes, all arriving at time zero, with total execution time of 10, 20 and 30 units, respectively. Each process spends the first 20% of execution time doing I/O, the next 70% of time doing computation, and the last 10% of time doing I/O again. The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst. Assume that all I/O operations can be overlapped as much as possible. For what percentage of time does the CPU remain idle?
0%  
10.6%  
30.0%  
89.4%

Question 65 Explanation:
Total time needed to complete the execution = 47
Idle time = 2+3 = 5
Percentage of Idle time = 5/47 × 100 =10.6%
Question 66 
Consider the following snapshot of a system running n processes. Process i is holding x_{i} instances of a resource R, 1 ≤ i ≤ n. Currently, all instances of R are occupied. Further, for all i, process i has placed a request for an additional y_{i} instances while holding the x_{i} instances it already has. There are exactly two processes p and q such that y_{p} = y_{q} = 0. Which one of the following can serve as a necessary condition to guarantee that the system is not approaching a deadlock?
min (x_{p}, x_{q}) < max_{k≠p,q}y_{k}  
x_{p} + x_{q} ≥ min_{k≠p,q}y_{k}  
max (x_{p}, x_{q}) > 1  
min (x_{p}, x_{q}) > 1 
Question 66 Explanation:
Deadlock refers stops the execution of process due to nonavailability of resources.
→ When two (or) more processes waiting for another process to release the resources.
→ P and Q can execute if they have sufficient resources, they don’t wait for extra resources (i.e., X_{p}+ X_{q}) required.
→ Option B can satisfies the corresponding equation i.e., X_{p}+ X_{q} >= min(Y_{k}) where k != p and k != q.
Here we have sufficient resources.
→ When two (or) more processes waiting for another process to release the resources.
→ P and Q can execute if they have sufficient resources, they don’t wait for extra resources (i.e., X_{p}+ X_{q}) required.
→ Option B can satisfies the corresponding equation i.e., X_{p}+ X_{q} >= min(Y_{k}) where k != p and k != q.
Here we have sufficient resources.
Question 67 
2 and 5
 
1 and 3
 
1 and 4
 
3 and 5

Question 67 Explanation:
Query 1 & 2 gives the same output for all not all data based its true because the salaries may be distinct variables. Statement 1 is true.
The customer with largest balance gets rank 1. Ties are broken with ranks are skipped.
So, both queries may doesn’t give same output. Statement 4 is correct.
The customer with largest balance gets rank 1. Ties are broken with ranks are skipped.
So, both queries may doesn’t give same output. Statement 4 is correct.
Question 68 
All queries return identical row sets for any database.
 
Query2 and Query4 return identical row sets for all databases but there exist databases for which Query1 and Query2 return different row sets.
 
There exist databases for which Query3 returns strictly fewer rows than Query2.
 
There exist databases for which Query4 will encounter an integrity violation at runtime.

Question 68 Explanation:
Consider Table examples as:
Query1 : Output
abcd
abcd
PQRS
Query 2 : Output
abcd
PQRS
Query 3 : Output
abcd
PQRS
Query 4 : Output
abcd
PQRS
Query 2 & Query 4 gives same results but Query 1 & Query 3 gives different results.
Query1 : Output
abcd
abcd
PQRS
Query 2 : Output
abcd
PQRS
Query 3 : Output
abcd
PQRS
Query 4 : Output
abcd
PQRS
Query 2 & Query 4 gives same results but Query 1 & Query 3 gives different results.
Question 69 
Plan 1 and Plan 2 will not output identical row sets for all databases.
 
A course may be listed more than once in the output of Plan 1 for some databases.
 
For x = 5000, Plan 1 executes faster than Plan 2 for all databases.
 
For x = 9000, Plan I executes slower than Plan 2 for all databases.

Question 69 Explanation:
Both plans are require the tables such as courses and enrolled to access the disks takes same time for both plans.
While analyze the plan1 and plan2 does lesser number of comparisons compared to plan1.
i) The join table consists of two tables will have more rows. So comparisons are needed to find amount greater than x.
ii) Join operation consists of more number of comparisons as the second table will have more rows in plan2 compared to plan1.
While analyze the plan1 and plan2 does lesser number of comparisons compared to plan1.
i) The join table consists of two tables will have more rows. So comparisons are needed to find amount greater than x.
ii) Join operation consists of more number of comparisons as the second table will have more rows in plan2 compared to plan1.
Question 70 
{CF}^{+} = {ACDEFG}  
{BG}^{+} = {ABCDG}
 
{AF}^{+} = {ACDEFG}  
{AB}^{+} = {ABCDFG}

Question 70 Explanation:
AB → CD
AF → D
DE → F
C → G
F → E
G → A
CF^{+} = {G,E,A,D,C,F} = {A,C,D,E,F,G} (✔️)
BG^{+} = {B,G,A,C,D} = {A,B,C,D,G} (✔️)
AF^{+} = {D,E,A,F} = {A,D,E,F} (❌)
AB^{+} = {A,B,C,D,G} (❌)
AF → D
DE → F
C → G
F → E
G → A
CF^{+} = {G,E,A,D,C,F} = {A,C,D,E,F,G} (✔️)
BG^{+} = {B,G,A,C,D} = {A,B,C,D,G} (✔️)
AF^{+} = {D,E,A,F} = {A,D,E,F} (❌)
AB^{+} = {A,B,C,D,G} (❌)
Question 71 
1  
n  
n+1  
2^{n} 
Question 71 Explanation:
No. of vertices with degree zero is
= no. of subsets with size less than or equal to 1
= n+1, because in question it is given that the two vertices are connected if and only if the corresponding sets intersect in exactly two elements.
= no. of subsets with size less than or equal to 1
= n+1, because in question it is given that the two vertices are connected if and only if the corresponding sets intersect in exactly two elements.
Question 72 
2^{n2}  
2^{n3} × 3  
2^{n1} 
Question 72 Explanation:
The degree of each subset with k elements will be
(k(_{c}))_{2} 2^{nk}
∴ We need to find 'k' value such that, the value will be maximum.[k should be an integer].
If you differentiate (k(_{c}))_{2} 2^{nk} w.r.t. k and equal to 0.
You will get k = 2/(log_{e})2 which is not an integer.
So you can see it like
∴ The maximum degree 3⋅2^{n3} at k=3 or k=4.
(k(_{c}))_{2} 2^{nk}
∴ We need to find 'k' value such that, the value will be maximum.[k should be an integer].
If you differentiate (k(_{c}))_{2} 2^{nk} w.r.t. k and equal to 0.
You will get k = 2/(log_{e})2 which is not an integer.
So you can see it like
∴ The maximum degree 3⋅2^{n3} at k=3 or k=4.
Question 73 
n  
n+2  
2^{n/2}  
2^{n} / n 
Question 73 Explanation:
Not connected nodes is n+1.
While other nodes are connected so that total number of connected components is (n+1)+1
(here we are adding 1 because it is connected corresponding remaining vertices)
= n+2
While other nodes are connected so that total number of connected components is (n+1)+1
(here we are adding 1 because it is connected corresponding remaining vertices)
= n+2
Question 74 
2.4 ns
 
2.3 ns  
1.8 ns
 
1.7 ns

Question 74 Explanation:
Cache size = 32 KB = 32 × 2^{10} B
Block size = 32 bytes
No. of blocks = 2 (2way set associative)
No. of combinations = Cache size / (Block size×No. of blocks) = (32×2^{10}B) / (32×2) = 29
Index bits = 9
No. of set bits = 5 (∵ cache block size is 32 bytes = 2^{5} bytes)
No. of Tag bits = 32  9  5 = 18
Hit latency = Multiplexer latency + latency
= 0.6 + (18/10)
= 0.6 + 1.8
= 2.4 ns
Block size = 32 bytes
No. of blocks = 2 (2way set associative)
No. of combinations = Cache size / (Block size×No. of blocks) = (32×2^{10}B) / (32×2) = 29
Index bits = 9
No. of set bits = 5 (∵ cache block size is 32 bytes = 2^{5} bytes)
No. of Tag bits = 32  9  5 = 18
Hit latency = Multiplexer latency + latency
= 0.6 + (18/10)
= 0.6 + 1.8
= 2.4 ns
Question 75 
2.4 ns  
2.3 ns  
1.8 ns  
1.7 ns 
Question 75 Explanation:
Hit latency = k/10 ns
For k,
∴ Hit latency = 17/1 = 1.7 ns
For k,
∴ Hit latency = 17/1 = 1.7 ns
Question 76 
1, 3, 5, 6, 8, 9
 
9, 6, 3, 1, 8, 5
 
9, 3, 6, 8, 5, 1
 
9, 5, 6, 8, 3, 1

Question 76 Explanation:
Question 77 
10, 7, 9, 8, 3, 1, 5, 2, 6, 4  
10, 9, 8, 7, 6, 5, 4, 3, 2, 1
 
10, 9, 4, 5, 7, 6, 8, 2, 1, 3
 
10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Question 77 Explanation:
Question 78 
The barrier implementation is wrong due to the use of binary semaphore S
 
The barrier implementation may lead to a deadlock if two barriers in invocations are
used in immediate succession
 
Lines 6 to 10 need not be inside a critical section
 
The barrier implementation is correct if there are only two processes instead of three

Question 78 Explanation:
If processarrived is because greater than 3. Then there is no possibility to be 3.
Hence, it is leads to deadlock.
Hence, it is leads to deadlock.
Question 79 
Lines 6 to 10 are simply replaced by process_arrived
 
At the beginning of the barrier the first process to enter the barrier waits until process_arrived becomes zero before proceeding to execute P(S).
 
Context switch is disabled at the beginning of the barrier and reenabled at the end.
 
The variable process_left is made private instead of shared.

Question 79 Explanation:
If processarrived is becomes zero then process_left becomes zero. Then deadlock may resolves.
Question 80 
0  
2048  
16384  
262144 
Question 80 Explanation:
[P1] Access A in row major order.
[P2] Access A in column major order.
No. of cache blocks=Cache size/Block size = 32KB / 128B = 32×2^{10}B / 128B = 2^{15} / 2^{7} = 256
No. of array elements in each block = Block size / Element size = 128B / 8B =16
Total misses for (P1)=Array size * No. of array elements / No. of cache blocks = (512×512) * 16 / 256=16384
[P2] Access A in column major order.
No. of cache blocks=Cache size/Block size = 32KB / 128B = 32×2^{10}B / 128B = 2^{15} / 2^{7} = 256
No. of array elements in each block = Block size / Element size = 128B / 8B =16
Total misses for (P1)=Array size * No. of array elements / No. of cache blocks = (512×512) * 16 / 256=16384
Question 81 
0  
1/16  
1/8  
16 
Question 81 Explanation:
Total misses for [P2] = 512 * 512 = 262144
(for every element there would be a miss)
M1/M2 = 16384/262144 = 1/16
(for every element there would be a miss)
M1/M2 = 16384/262144 = 1/16
Question 82 
B1, B5, B3, B4, B2  
B1, B3, B5, B2, B4  
B1, B5, B2, B3, B4
 
B1, B3, B4, B5, B2

Question 82 Explanation:
Start Depth First traversal from B1 . B5 is connected to port 1 of B1 so B5 will be traversed after B1.
Port1 of B5 is connected to port1 of B2 and port2 of B3. B2 is connected with lower index port so B2 is traversed next.
Port 2 Both B3 and B4 is connected with port1 of B2, but B3 is Closer to root so B3 will be traversed next.
Depth First traversal is B1,B5,B2,B3,B4.
Port1 of B5 is connected to port1 of B2 and port2 of B3. B2 is connected with lower index port so B2 is traversed next.
Port 2 Both B3 and B4 is connected with port1 of B2, but B3 is Closer to root so B3 will be traversed next.
Depth First traversal is B1,B5,B2,B3,B4.
Question 83 
Question 83 Explanation:
Use Spanning tree generated in previous question.
Question 84 
Which one of the following grammars generates the language L = {a^{i}b^{j}  i≠j}?
S→ACCB C→aCbab A→aAϵ B→Bbϵ  
S→aSSbab
 
S→ACCB C→aCbϵ A→aAϵ B→Bbϵ  
S→ACCB C→aCbϵ A→aAa B→Bbb 
Question 84 Explanation:
The language have all the strings in which a’s comes before b’s and number of a’s never equal to b’s. The grammars in Option A, B and C generates string “ab” in which number of a’s are equal to b’s, hence they are wrong. But option D generates all the string which is in L.
Question 85 
In the correct grammar of above question, what is the length of the derivation (number of steps starting from S) to generate the string a^{l}b^{m} with l≠m?
max(l,m)+2  
l+m+2
 
l+m+3
 
max(l, m)+3

Question 85 Explanation:
The correct grammar for L = {a^{i}b^{j}  i≠j} is
S → ACCB C → aCbϵ A → aAa B → Bbb
Assume a string: “aaabb” in this l=3 and m=2
The steps are:
Step1: S> AC
Step 2: S> aC By production: A> a
Step 3: S> aaCb By production: C> aCb
Step 4: S> aaaCbb By production: C> aCb
Step 5: S> aaabb By production: C> ϵ
Hence, it is clear that the correct option is A, i.e. max(l,m)+2
S → ACCB C → aCbϵ A → aAa B → Bbb
Assume a string: “aaabb” in this l=3 and m=2
The steps are:
Step1: S> AC
Step 2: S> aC By production: A> a
Step 3: S> aaCb By production: C> aCb
Step 4: S> aaaCbb By production: C> aCb
Step 5: S> aaabb By production: C> ϵ
Hence, it is clear that the correct option is A, i.e. max(l,m)+2
There are 85 questions to complete.