R1:
a+a=2a
The set (a,a) is reflexive.
The set representation (a,a), (b,b) is also Symmetric.
The set representation is Transitive.
So, this is Equivalence.
R2:
a+a≠2a
The (a,a) is non-reflexive.
R3:
a⋅a>0 → Reflexive
a⋅b>0 and b⋅a>0 → Symmetric
a⋅b>0, b⋅c>0 then c⋅a>0 → Transitive
The relation R3 is equivalence relation.
R4:
|a - a| ≤ 2, which is not possible, not Reflexive.
R1 & R3 are equivalence, R2 & R4 are not.

F1 is satisfiable; F2 is valid.

For S1 we can construct DFA. S1 represents the string contains even no. of 0's. So S1 is regular.
For S2, DFA is not possible which is not regular.

Context free languages closed under Union, concatenation and kleen star. But not close under intersection and complementation.

If NFA contains N, then possible number of states in possible DFA is 2^N.
If NFA have two states {1}{2} = 2
Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 2² = 2^N

Spatial locality refers to the use of data elements within relatively close storage locations. To exploit the spatial locality, more than one word are put into cache block.
The temporal locality refers to reuse of data elements with a smaller regular intervals.

In a system with virtual memory context switch includes extra overhead in switching of address spaces.

Communication is only possible when READY signal is set. So a low memory can be connected to 8085 by using READY signal.

If stack pointer register is not available then activation records in the stack cannot be created. So it cannot have subroutine call instruction.

⇒ y'z + xy

To execute privileged instructions, system services can be obtained using software interrupt.

For switching between privileged to non-privileged area, non-privileged instruction is used, without interrupt.

In worst case Randomized quicksort execution time complexity is same as quicksort.

Parent Node is at index: ⌊i/2⌋
Left Child is at index: 2i
Right child is at index: 2*i+1

f(n) = n²logn; g(n) = n(logn)¹⁰
Cancel nlogn from f(n), g(n)
f(n) = n; g(n) = (logn)⁹
n is too large than (logn)⁹
So f(n)! = O(g(n)) and g(n) = O(f(n))

Relocation can change the assigned address of data and code in the program.

Option B: LL parser is a top-down parser for a subset of context-free languages. It parses the input from Left to right, performing Left most derivation of the sentence.
Option C: LALR is more powerful than SLR.
Option D: An ambiguous grammar can never be LR (k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is.

First we know what is throughput. It means total number of tasks executed per unit time.SJF executes shortest job very early so throughput increases in the case of SJF.

Swap space is an area on disk that temporarily holds a process memory image.  
When memory is full and process needs memory, inactive parts of process are put in swap space of disk.

Belady’s Anomaly more number of frames = More page faults.
See Belady’s anomaly is the name given to the phenomenon where increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern.
This phenomenon is commonly experienced in following page replacement algorithms: First in first out (FIFO), Second chance algorithm, Random page replacement algorithm.

Disk driver is software which enables communication between internal hard disk (or drive) and computer.

If the given realations are to be lossless then
R₁∩R₂ ≠ 0
Given R₁(A,B), R₂
R₁∩R₂= 0
Not lossless.
The given relation decomposed into R₁(A,B) and R₂(C,D) and there are only two functional dependencies A→B and C→D. So the given decomposition is dependency preserving.

(a) Finding a adjaceny vertex for the given vertex is too simple i.e., Adj(X,Y).
(b) Finding a self loop is also simple (Oop(X,X))
(c) If a → b, b → c then c!=a, finding this is also simple.
(d) List all the elements reachable from a given vertex is too difficult in Relational Algebra.

(a) A=a for all r
(b) Display table
(c) A=a for all Tables r and s

If the last digit is 0 then

If last digit is (2, 4, 6, 8)

Total possibilities = 504 + 1792 = 2296

S1: Consider A = {2,4,6,8,10,...} set of all even numbers
B = {2,3,5,7,11,13,...} set of prime numbers
C = {1,3,5,7,...} set of odd numbers
(B∪C) = {1,2,3,5,7,...}
A∩(B∪C) = {2}
Which is finite, S1 is true.
S2: Consider A=5+√3 Irrational
B=5-√3 Irrational
A+B=10 Rational
A+B, which is rational number, S2 is true.

S1: f(E∪F) = f(E)∪f(F)
The both LHS and RHS contains the same element in E and F.
So, S1 is true.
S2: f(E∩F) = f(E)∩f(F)
E and F are partitions of A.
f(E)∩f(F) = ϕ
f(ϕ) is not defined, but f(E)∩f(F)=1.
So, S2 is false.

Probability of all accidents on sunday = 1/7⁷
Such as total no. of days in a week = 7
Total probability = 7 × 1/7⁷ = 1/7⁶

A DFA which is no. of a's divisible by 6 consists of 6 states i.e., mod6 results 0,1,2,3,4,5.
Same as b's divisible by 8 contains 8 state.
Total no. of states is = 8 * 6 = 48

L1 = {ww|w∈{a,b}*}
⇒ This is not regular language. We can't be able to identify where the 'w' will ends and where the next 'w' starts.
L2 = {ww^R|w∈{a,b}*, w^R is the reverse of w}
⇒ This also not a regular language. We can't identify where 'w' ends.
L4 = {0ⁱ²|i is an integer}
= {0ⁱ*0ⁱ|i is an integer}
⇒ This is also not a regular language. We can't identify where 0ⁱ ends.
L3 = {0²ⁱ|i is an integer}
⇒ This is regular. We can easily find whether a string is even or not.

The given X is a Halting problem. So which is to be undecidable but partially decidable.

Given clock is +edge triggered.
See the first positive edge. X is 0, and hence the output is 0, because
Y = Q_1N = D₁×Q₀' = 0⋅Q₀' = 0
At second +edge, X is 1 and Q₀' is also 1. So output is 1 (when second +ve edge of the clock arrives, Q₀' would surely be 1 because the setup time of flip flop is given as 20ns and clock period is ≥ 40ns).
At third +ve edge, X is 1 and Q₀' is 0, so output is 0.
Now output never changes back to 1 as Q₀' is always 0 and when Q₀' finally becomes 1, X is 0.
Hence option (A) is the correct answer.

⇒ Array implementation can be done by Indexed addressing.
⇒ Writing relocatable code can be done by Base Register addressing by changing the value of Base Register.
⇒ While passing an array as parameter we use pointer and hence can use Indirect addressing.

(539)₁₀ = (0010 0001 1011)₂
For (-539)₁₀ = (1101 1110 0100)₂
1's complement = (1101 1110 0100)₂
2's complement = (1101 1110 0101)₂
= (DE5)₁₆

g = (a and x1′) or (b and x1)
g = (1 and x1’) or (0 and x1)
g = x1’
f = ac’ + bc
f = (a and x2′) or (b and x2)
f = (g and x2′) or (x1 and x2)
f = x1’x2’ + x1x2

T1: SP → MAR, 2 cycles (as SP is 16 bits and data bus is 8 bits so needs 2 cycles to move data)
T2: 8 → MBR, 1 cycle
T3: M[MAR] ← MBR, 2 cycles (As it is a memory operation)
So, total 5 clock cycles.

d(r,u) and d(r, v) will be equal when u and v are at same level, otherwise d(r,u) will be less than d(r,v).

With n vertices no. of possible edges = ⁿ C ₂
Each subset of these edges will be form a graph.
No. of possible undirected graphs is 2^{(n C ₂)
⇒ 2(n(n-1)/2)}

Minimum number of stacks of size n required to implement a queue of size n is two. With the help of two stacks we can able to implement a queue.

Here, variable x of func1 points to address of variable y.
And variable y and z of func1 points to address of variable x.
Therefore, y = y+4 ⇒ y = 10+4 = 14
and z = x+y+z ⇒ z = 14+14+3 = 31
z will be stored back in k.
Hence, x=31 and y will remain as it is (y=3).
Hence, answer is (B).

[P1] → May cause error because the function is returning the address of locally declared variable.
[P2] → It will cause problem because px is in int pointer that is not assigned with any address and we are doing dereferencing.
[P3] → It will work because memory will be stored in px that can be use further. Once function execution completes this will exist in Heap.

n=3
W(n)=W(3)
Procedure W(var x; int)
begin
x = x+1 = 3+1 = 4
Print x → Print x=4
end

Scheduler process doesn’t interrupt any process, it’s Job is to select the processes for following three purposes.

No. of entries in pge table = 2³²/ 2¹² = 2²⁰
Frame size = 2²⁶ / 2¹² = 2¹⁴
PT have to be stored in one frame so entry size must be 2 bytes, hence size of PT = 2²⁰ * 2 = 2 MB

To ensure the mutual exclusion, we have to take care that ‘turn’ value which is ‘j’ so we should not allow that process in CS which is having flag[j] = true.

We have, R (A, B, C, D) and the Functional Dependency set = {AB→C, C→AD}. We decompose it as R1(A, B, C) and R2(C, D). This preserves all dependencies and the join is lossless too, but the relation R1 is not in BCNF. In R1 we keep ABC together otherwise preserving {AB→C} will fail, but doing so also causes {C→A} to appear in R1. {C→A} violates the condition for R1 to be in BCNF as C is not a super key. Condition that all relations formed after decomposition should be in BCNF is not satisfied here.

(a)
The function is self dual because
→ There is no mutually exclusive pair.
→ No. of minterms = No. of maxterms
(b)
Write Minimal POS.

(b) 2 distinct MST's.
(c) Yes, it always. Because 'the edge weight 2 is unique'.
(d) Yes, it always. Because 'the edge weight 9 is unique'.