## UGC NET CS 2007 June-Paper-2

Question 1 |

The following deterministic finite automata recognizes :

Set of all strings containing ‘ab’ | |

Set of all strings containing ‘aab’ | |

Set of all strings ending in ‘abab’ | |

None of the above |

Question 1 Explanation:

There is no final state in the given deterministic finite automata so it can't accept any string. Hence the answer is option(D)

Question 2 |

Depth ion travels of the following directed graph is :

A B C D E F | |

A B D E F C | |

A C E B D F | |

None of the above |

Question 2 Explanation:

To find depth ion traverse using DFS.

Option-A: It is ruled out because we can’t move after C to D. It is violating DFS property.

Option-B: It is following actual DFS structure.

Option-C: It is ruled out because after visiting E we can’t visit B again. It is violating DFS properties.

Option-A: It is ruled out because we can’t move after C to D. It is violating DFS property.

Option-B: It is following actual DFS structure.

Option-C: It is ruled out because after visiting E we can’t visit B again. It is violating DFS properties.

Question 3 |

The maximum number of nodes in a binary tree of depth 10 :

1024 | |

2 ^{10} - 1 | |

1000 | |

None of the above |

Question 3 Explanation:

→ The depth of binary tree starts from 0 but not 1.

→ To find maximum number of nodes in a binary tree of depth using formula is

= 2

= 2

= 2048-1

= 2047

→ To find maximum number of nodes in a binary tree of depth using formula is

= 2

^{h+1}-1= 2

^{11}-1= 2048-1

= 2047

Question 4 |

The regular expression given below describes : r=(1+01)* (0+λ)

Set of all string not containing ‘11’ | |

Set of all string not containing ‘00’ | |

Set of all string containing ‘01’ | |

Set of all string ending in ‘0’ |

Question 4 Explanation:

L= { λ, 0, 1λ, 01λ, 10, 010, 110, .............}

According to the language L generated by given regular expression

Option(A) is incorrect because L contains 110.

Option(B) is correct because no string is containing 00

Option(C) is incorrect because not all strings in L are containing 01 example 0 in L does not contain 01.

Option(D) is incorrect because L contains 1λ is there in L which is not ending with 0.

Hence correct answer is option (B)

According to the language L generated by given regular expression

Option(A) is incorrect because L contains 110.

Option(B) is correct because no string is containing 00

Option(C) is incorrect because not all strings in L are containing 01 example 0 in L does not contain 01.

Option(D) is incorrect because L contains 1λ is there in L which is not ending with 0.

Hence correct answer is option (B)

Question 5 |

Which of the following language is regular :

L = { a ^{n} b^{n}| n ≥ 1 } | |

L = { a ^{n} b^{m} c^{n }d^{m}|n, m ≥ 1 } | |

L = { a ^{n} b^{m}|n, m ≥ 1 } | |

L = { a ^{n} b^{m} c^{n}|n, m ≥ 1 } |

Question 5 Explanation:

Language generated in Option (A) requires a memory element to count an equal number of b's after a. And since regular languages are accepted by finite automata which do not have a memory element. Hence Option (A) language is not Regular.

Language generated in Option (B) requires a memory element and a read-write head which can move in both directions to count equal numbers of a's and c's , and b's and d's. And since regular languages are accepted by finite automata which do not have a memory element and a read-write head which can move in both directions. Hence Option (A) language is not Regular.

Language generated in Option (C) is regular because the number of a's and b's does not necessarily need to be the same which means no memory element is required. Hence it is a regular language.

Language generated in Option (D) requires a memory element to count an equal number of c's after a. And since regular languages are accepted by finite automata which do not have a memory element. Hence Option (A) language is not Regular. The language generated here is context free language which can be accepted by pushdown automata.

Language generated in Option (B) requires a memory element and a read-write head which can move in both directions to count equal numbers of a's and c's , and b's and d's. And since regular languages are accepted by finite automata which do not have a memory element and a read-write head which can move in both directions. Hence Option (A) language is not Regular.

Language generated in Option (C) is regular because the number of a's and b's does not necessarily need to be the same which means no memory element is required. Hence it is a regular language.

Language generated in Option (D) requires a memory element to count an equal number of c's after a. And since regular languages are accepted by finite automata which do not have a memory element. Hence Option (A) language is not Regular. The language generated here is context free language which can be accepted by pushdown automata.

Question 6 |

2’s complement of -100 is :

00011100 | |

10011101 | |

10011100 | |

11100100 |

Question 6 Explanation:

Question 7 |

Which of the following expression remove hazard form : xy+zx’ ?

xy+zx’ | |

xy+zx’ | |

xy+zx’+yz | |

xy+zx’+wz |

Question 7 Explanation:

→ A static hazard occurs if a circuit produces incorrect output value momentarily before stabilizing to its correct value.

→ Generally Hazard occurs due to different delays in different paths of the circuit.

→ In the expression xy +zx’ the variable x is in true form in one term(xy) and in complement in other term(zx').

→ Delay occurs due to the presence of NOT gate.

If input xyz=111 then output is 1.

If input xyz=011 then output stays momentarily in state 0 then settles in state 1.

→ Adding the term yz(select y from xy and z from zx') eliminates the hazard.

→ Generally Hazard occurs due to different delays in different paths of the circuit.

→ In the expression xy +zx’ the variable x is in true form in one term(xy) and in complement in other term(zx').

→ Delay occurs due to the presence of NOT gate.

If input xyz=111 then output is 1.

If input xyz=011 then output stays momentarily in state 0 then settles in state 1.

→ Adding the term yz(select y from xy and z from zx') eliminates the hazard.

Question 8 |

How many 1’s are present in the binary representation of 15*256 + 5*16 + 3 :

8 | |

9 | |

10 | |

11 |

Question 8 Explanation:

Step-1: The precedence to given decimal number is (15*256) + (5*16) + 3

Step-2: 3840+80+3=(3923)

Step-3: Convert decimal number into binary

(3923)

Step-4: Total number of 1’s are 8.

Step-2: 3840+80+3=(3923)

^{10}Step-3: Convert decimal number into binary

(3923)

^{10}= (111101010011 )_{2}Step-4: Total number of 1’s are 8.

Question 9 |

If A⊕B=C , then :

A ⊕ C = B | |

B ⊕ C = A | |

A ⊕ B ⊕ C = 1 | |

A ⊕ B ⊕ C = 0 | |

None of the above |

Question 9 Explanation:

Given that A⊕B=C

1) A⊕B⊕ C = C⊕C

A⊕B⊕ C = 0 (Since C⊕C =0)

option D is correct.

So option C is not correct.

2) From step 1, we know that A⊕B⊕ C = 0

A⊕B⊕ C ⊕ B= 0 ⊕ B

A ⊕ C = B (Since B ⊕ B= 0)

So option A is correct.

3) From step 1, we know that A⊕B⊕ C = 0

A⊕B⊕ C ⊕ A= 0 ⊕ A

B ⊕ C = A (Since A ⊕ A =0)

So option B is also correct.

1) A⊕B⊕ C = C⊕C

A⊕B⊕ C = 0 (Since C⊕C =0)

option D is correct.

So option C is not correct.

2) From step 1, we know that A⊕B⊕ C = 0

A⊕B⊕ C ⊕ B= 0 ⊕ B

A ⊕ C = B (Since B ⊕ B= 0)

So option A is correct.

3) From step 1, we know that A⊕B⊕ C = 0

A⊕B⊕ C ⊕ A= 0 ⊕ A

B ⊕ C = A (Since A ⊕ A =0)

So option B is also correct.

Question 10 |

What is the maximum counting speed of a 4-bit binary counter which is composed of Flip-Flop with a propagation delay of 25ns ?

1MHz | |

10MHz | |

100MHz | |

4MHz |

Question 10 Explanation:

Question is about frequency of the counter.

Frequency = 1/ Time

Binary counter is ripple counter where the output one flip flop is clock input to next flip flop.

So, maximum delay(time)= 4*25ns = 100 ns.

frequency= 1/100 ns

= 10 MHz.

Frequency = 1/ Time

Binary counter is ripple counter where the output one flip flop is clock input to next flip flop.

So, maximum delay(time)= 4*25ns = 100 ns.

frequency= 1/100 ns

= 10 MHz.

Question 11 |

The following loop in ‘C’ :

int i=0;

while (i++ < 0)

i-- ;

int i=0;

while (i++ < 0)

i-- ;

will terminate | |

will go into an infinite loop | |

will give compilation error | |

will never be executed |

Question 11 Explanation:

#include

void main()

{

int i=0;

while(i++ < 0)

{

i--;

printf("%d",i);

}

}

/* It will terminate null value */

void main()

{

int i=0;

while(i++ < 0)

{

i--;

printf("%d",i);

}

}

/* It will terminate null value */

Question 12 |

In case of right shift bitwise operator in ‘C’ language, after shifting n bits, the leftmost n bits :

are always filled with zeros | |

are always filled with ones | |

are filled with zeros or ones and is machine dependent | |

none of the above |

Question 12 Explanation:

In case of right shift bitwise operator in ‘C’ language, after shifting n bits, the leftmost n bits are filled with zeros or ones and is machine dependent.

Example:

Input: positive number→ It will filled with zeros

Input: Negative number → it will filled with ones

Option-C is more appropriate answer.

Example:

Input: positive number→ It will filled with zeros

Input: Negative number → it will filled with ones

Option-C is more appropriate answer.