## Gate-2001

Question 1 |

S1 and S2 are both true | |

S1 is true, S2 is false | |

S1 is false, S2 is true | |

S1 and S2 are both false |

Question 1 Explanation:

Question 2 |

R1 and R2 are equivalence relations, R3 and R4 are not | |

R1 and R3 are equivalence relations, R2 and R4 are not | |

R1 and R4 are equivalence relations, R2 and R3 are not | |

R1, R2, R3 and R4 are all equivalence relations |

Question 2 Explanation:

__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.

Question 3 |

F1 is satisfiable, F2 is valid | |

F1 unsatisfiable, F2 is satisfiable | |

F1 is unsatisfiable, F2 is valid | |

F1 and F2 are both satisfiable |

Question 3 Explanation:

F1 is satisfiable; F2 is valid.

Question 4 |

Only S1 is correct | |

Only S2 is correct | |

Both S1 and S2 are correct | |

None of S1 and S2 is correct |

Question 4 Explanation:

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.

For S2, DFA is not possible which is not regular.

Question 5 |

Which of the following statements is true?

If a language is context free it can always be accepted by a deterministic push-down automaton | |

The union of two context free languages is context free | |

The intersection of two context free languages is context free | |

The complement of a context free language is context free |

Question 5 Explanation:

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

Question 6 |

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

N ^{2} | |

2 ^{N} | |

2N | |

N! |

Question 6 Explanation:

If NFA contains N, then possible number of states in possible DFA is 2

If NFA have two states {1}{2} = 2

Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 2

^{N}.If NFA have two states {1}{2} = 2

Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 2

^{2}= 2^{N}Question 7 |

More than one word is put in one cache block to

exploit the temporal locality of reference in a program | |

exploit the spatial locality of reference in a program | |

reduce the miss penalty | |

none of the above |

Question 7 Explanation:

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.

The temporal locality refers to reuse of data elements with a smaller regular intervals.

Question 8 |

Which of the following statements is false?

Virtual memory implements the translation of a program’s address space into physical memory address space | |

Virtual memory allows each program to exceed the size of the primary memory | |

Virtual memory increases the degree of multiprogramming | |

Virtual memory reduces the context switching overhead |

Question 8 Explanation:

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

Question 9 |

A low memory can be connected to 8085 by using

INTER | |

HOLD | |

READY |

Question 9 Explanation:

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

Question 10 |

Suppose a processor does not have any stack pointer register. Which of the following statements is true?

It cannot have subroutine call instruction | |

It can have subroutine call instruction, but no nested subroutine calls | |

Nested subroutine calls are possible, but interrupts are not | |

All sequences of subroutine calls and also interrupts are possible |

Question 10 Explanation:

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

Question 11 |

xy+y'z | |

wx'y'+xy+xz | |

w'x+y'z+xy | |

xz+y |

Question 11 Explanation:

⇒ y'z + xy

Question 12 |

A processor needs software interrupt to

test the interrupt system of the processor | |

implement co-routines | |

obtain system services which need execution of privileged instructions | |

return from subroutine |

Question 12 Explanation:

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

Question 13 |

A CPU has two modes-privileged and non-privileged. In order to change the mode from privileged to non-privileged

a hardware interrupt is needed | |

a software interrupt is needed | |

a privileged instruction (which does not generate an interrupt) is needed | |

a non-privileged instruction (which does not generate an interrupt is needed |

Question 13 Explanation:

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

Question 14 |

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

O(n) | |

O(n log n) | |

O(n ^{2}) | |

O(n!) |

Question 14 Explanation:

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

Question 15 |

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i≤n), the index of the parent is

Question 15 Explanation:

Parent Node is at index: ⌊i/2⌋

Left Child is at index: 2i

Right child is at index: 2*i+1

Left Child is at index: 2i

Right child is at index: 2*i+1

Question 16 |

Let f(n) = n

^{2}logn and g(n) = n(logn)^{10}be two positive functions of n. Which of the following statements is correct?f(n) = O(g(n) and g(n) ≠ O(f(n)) | |

g(n) = O(f(n) and f(n) ≠ O(g(n)) | |

f(n) ≠ O(g(n)) and g(n) ≠ O(f(n)) | |

f(n) = O(g(n)) and g(n) = O(f(n)) |

Question 16 Explanation:

f(n) = n

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))

^{2}logn; g(n) = n(logn)^{10}Cancel nlogn from f(n), g(n)

f(n) = n; g(n) = (logn)

^{9}n is too large than (logn)

^{9}So f(n)! = O(g(n)) and g(n) = O(f(n))

Question 17 |

The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called

Assembly | |

Parsing | |

Relocation | |

Symbol resolution |

Question 17 Explanation:

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

Question 18 |

Which of the following statements is false?

An unambiguous grammar has same leftmost and rightmost derivation | |

An LL(1) parser is a top-down parser | |

LALR is more powerful than SLR | |

An ambiguous grammar can never be LR(k) for any k |

Question 18 Explanation:

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.

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.

Question 19 |

Consider a set of n tasks with known runtimes r_{1}, r_{2}, ..., r_{n} to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput?

Round-Robin | |

Shortest-Job-First | |

Highest-Response-Ratio-Next | |

First-Come-First-Served |

Question 19 Explanation:

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.

Question 20 |

Where does the swap space reside?

RAM | |

Disk | |

ROM | |

On-chip cache |

Question 20 Explanation:

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.

When memory is full and process needs memory, inactive parts of process are put in swap space of disk.

Question 21 |

Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will

always decrease the number of page faults | |

always increase the number of page faults | |

sometimes increase the number of page faults | |

never affect the number of page faults |

Question 21 Explanation:

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.

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.

Question 22 |

Which of the following requires a device driver?

Register | |

Cache | |

Main memory | |

Disk |

Question 22 Explanation:

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

Question 23 |

Consider a schema R(A,B,C,D) and functional dependencies A → B and C → D. Then the decomposition of R into R

_{1}(AB) and R_{2}(CD) isdependency preserving and lossless join | |

lossless join but not dependency preserving | |

dependency preserving but not lossless join | |

not dependency preserving and not lossless join |

Question 23 Explanation:

If the given realations are to be lossless then

R

Given R

R

Not lossless.

The given relation decomposed into R

R

_{1}∩R_{2}≠ 0Given R

_{1}(A,B), R_{2}R

_{1}∩R_{2}= 0Not lossless.

The given relation decomposed into R

_{1}(A,B) and R_{2}(C,D) and there are only two functional dependencies A→B and C→D. So the given decomposition is dependency preserving.Question 24 |

Suppose the adjacency relation of vertices in a graph is represented in a table Adj(X,Y). Which of the following queries cannot be expressed by a relational algebra expression of constant length?

List of all vertices adjacent to a given vertex | |

List all vertices which have self loops | |

List all vertices which belong to cycles of less than three vertices | |

List all vertices reachable from a given vertex |

Question 24 Explanation:

(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.

(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.

Question 25 |

Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. Then the relational algebra expression σ

_{A=a}(r⋈s) is always equal toσ _{A=a} (r) | |

r | |

σ _{A=a} (r)⨝s | |

None of the above |

Question 25 Explanation:

(a) A=a for all r

(b) Display table

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

(b) Display table

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

Question 26 |

How many 4-digit even numbers have all 4 digits distinct?

2240 | |

2296 | |

2620 | |

4536 |

Question 26 Explanation:

If the last digit is 0 then

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

Total possibilities = 504 + 1792 = 2296

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

Total possibilities = 504 + 1792 = 2296

Question 27 |

Only S1 is correct | |

Only S2 is correct | |

Both S1 and S2 are correct | |

None of S1 and S2 is correct |

Question 27 Explanation:

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.

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.

Question 28 |

Only S1 is correct | |

Only S2 is correct | |

Both S1 and S2 are correct | |

None of S1 and S2 is correct |

Question 28 Explanation:

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.

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.

Question 29 |

Seven (distinct) car accidents occurred in a week. What is the probability that they all occurred on the same day?

Question 29 Explanation:

Probability of all accidents on sunday = 1/7

Such as total no. of days in a week = 7

Total probability = 7 × 1/7

^{7}Such as total no. of days in a week = 7

Total probability = 7 × 1/7

^{7}= 1/7^{6}Question 30 |

Consider a DFA over Σ = {a,b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?

8 | |

14 | |

15 | |

48 |

Question 30 Explanation:

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

Same as b's divisible by 8 contains 8 state.

Total no. of states is = 8 * 6 = 48

Question 31 |

Only L1 and L2 | |

Only L2, L3 and L4 | |

Only L3 and L4 | |

Only L3 |

Question 31 Explanation:

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

⇒ This also not a regular language. We can't identify where 'w' ends.

L4 = {0

= {0

⇒ This is also not a regular language. We can't identify where 0

L3 = {0

⇒ This is regular. We can easily find whether a string is even or not.

⇒ 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

^{i2}|i is an integer}= {0

^{i}*0^{i}|i is an integer}⇒ This is also not a regular language. We can't identify where 0

^{i}ends.L3 = {0

^{2i}|i is an integer}⇒ This is regular. We can easily find whether a string is even or not.

Question 32 |

X is decidable | |

X is undecidable but partially decidable | |

X is undecidable and not even partially decidable | |

X is not a decision problem |

Question 32 Explanation:

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

Question 33 |

Question 33 Explanation:

Given clock is +edge triggered.

See the first positive edge. X is 0, and hence the output is 0, because

Y = Q

_{1N}= D

_{1}×Q

_{0}' = 0⋅Q

_{0}' = 0

At second +edge, X is 1 and Q

_{0}' is also 1. So output is 1 (when second +ve edge of the clock arrives, Q

_{0}' 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

_{0}' is 0, so output is 0.

Now output never changes back to 1 as Q

_{0}' is always 0 and when Q

_{0}' finally becomes 1, X is 0.

Hence option (A) is the correct answer.

Question 34 |

(X, III) (Y, I) (Z, II) | |

(X, II) (Y, III) (Z, I) | |

(X, III) (Y, II) (Z, I) | |

(X, I) (Y, III) (Z, II) |

Question 34 Explanation:

⇒ 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.

⇒ 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.

Question 35 |

The 2’s complement representation of (-539)

_{10}in hexadecimal isABE | |

DBC | |

DE5 | |

9E7 |

Question 35 Explanation:

(539)

For (-539)

1's complement = (1101 1110 0100)

2's complement = (1101 1110 0101)

= (DE5)

_{10}= (0010 0001 1011)_{2}For (-539)

_{10}= (1101 1110 0100)_{2}1's complement = (1101 1110 0100)

_{2}2's complement = (1101 1110 0101)

_{2}= (DE5)

_{16}Question 36 |

f = x1' + x2 | |

f = x1'x2 + x1x2' | |

f = x1x2 + x1'x2' | |

f = x1 + x2' |

Question 36 Explanation:

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

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

Question 37 |

1,3,4,6,7,5,2 | |

1,2,5,3,7,6,4 | |

1,2,7,3,5,6,4 | |

1,6,5,7,2,3,4 |

Question 37 Explanation:

Question 38 |

2 | |

3 | |

4 | |

5 |

Question 38 Explanation:

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.

T2: 8 → MBR, 1 cycle

T3: M[MAR] ← MBR, 2 cycles (As it is a memory operation)

So, total 5 clock cycles.

Question 39 |

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?

d(r,u) | |

d(r,u)>d(r,v) | |

d(r,u)≤d(r,v) | |

None of the above |

Question 39 Explanation:

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).

Question 40 |

How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v

_{1}, v_{2}, ...,v_{n}} of n vertices?2 ^{n} | |

n! | |

Question 40 Explanation:

With n vertices no. of possible edges =

Each subset of these edges will be form a graph.

No. of possible undirected graphs is 2

^{n}C_{2}Each subset of these edges will be form a graph.

No. of possible undirected graphs is 2

^{(n C 2) ⇒ 2(n(n-1)/2)}Question 41 |

What is the minimum number of stacks of size n required to implement a queue of size n?

One | |

Two | |

Three | |

Four |

Question 41 Explanation:

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.

Question 42 |

10, 3 | |

31, 3 | |

27, 7 | |

None of the above |

Question 42 Explanation:

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).

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).

Question 43 |

Only P3 | |

Only P1 and P3 | |

Only P1 and P2 | |

P1, P2 and P3 |

Question 43 Explanation:

[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.

[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.

Question 44 |

10 | |

11 | |

3 | |

None of the above |

Question 44 Explanation:

n=3

W(n)=W(3)

Procedure W(var x; int)

begin

x = x+1 = 3+1 = 4

Print x → Print x=4

end

W(n)=W(3)

Procedure W(var x; int)

begin

x = x+1 = 3+1 = 4

Print x → Print x=4

end

Question 45 |

Which of the following does not interrupt a running process?

A device | |

Timer | |

Scheduler process | |

Power failure |

Question 45 Explanation:

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

Question 46 |

Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the page size is 4 KB, what is the approximate size of the page table?

16 MB | |

8 MB | |

2 MB | |

24 MB |

Question 46 Explanation:

No. of entries in pge table = 2

Frame size = 2

PT have to be stored in one frame so entry size must be 2 bytes, hence size of PT = 2

^{32}/ 2^{12}= 2^{20}Frame size = 2

^{26}/ 2^{12}= 2^{14}PT have to be stored in one frame so entry size must be 2 bytes, hence size of PT = 2

^{20}* 2 = 2 MBQuestion 47 |

flag[j]=true and turn=i | |

flag[j]=true and turn=j | |

flag[i]=true and turn=j | |

flag[i]=true and turn=i |

Question 47 Explanation:

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.

Question 48 |

R(A,B,C,D) is a relation. Which of the following does not have a lossless join, dependency preserving BCNF decomposition?

A → B, B → CD | |

A → B, B → C, C → D | |

AB → C, C → AD | |

A → BCD |

Question 48 Explanation:

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.

Question 49 |

Which of the following relational calculus expressions is not safe?

{t|∃u ∈ R _{1} (t[A] = u[A])∧ ¬∃s ∈ R_{2} (t[A] = s[A])} | |

{t|∀u ∈ R _{1} (u[A]= "x" ⇒ ∃s ∈ R_{2} (t[A] = s[A] ∧ s[A] = u[A]))} | |

{t|¬(t ∈ R _{1})} | |

{t|∃u ∈ R _{1} (t[A] = u[A])∧ ∃s ∈ R_{2} (t[A] = s[A])} |

Question 50 |

A tuple (z,w) with z > y is deleted | |

A tuple (z,w) with z > x is deleted | |

A tuple (z,w) with w < x is deleted | |

The deletion of (x,y) is prohibited |

Question 54 |

Give a deterministic PDA for the language L = {a

^{n}cb^{2n}|n ≥ 1} over the alphabet Σ = {a,b,c}. Specify the acceptance state.Theory Explanation is given below. |

Question 58 |

Theory Explanation is given below. |

Question 58 Explanation:

(a)

The function is self dual because

→ There is no mutually exclusive pair.

→ No. of minterms = No. of maxterms

(b)

Write Minimal POS.

The function is self dual because

→ There is no mutually exclusive pair.

→ No. of minterms = No. of maxterms

(b)

Write Minimal POS.

Question 59 |

Theory Explanation is given below. |

Question 59 Explanation:

Question 63 |

Theory Explanation is given below. |

Question 63 Explanation:

(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'.

(c) Yes, it always. Because 'the edge weight 2 is unique'.

(d) Yes, it always. Because 'the edge weight 9 is unique'.

There are 70 questions to complete.