61.
Given the following two statements:

A. L = {w|n_{a}(w)
= n_{b}(w)} is deterministic context free language, but not linear.

B. L = {a^{n}
b^{n}} U {a^{n} b^{2n}} is linear, but not
deterministic context free language.

Which of the
following options is correct?

(1) Both (A)
and (B) are false.

(2) Both (A)
and (B) are true.

(3) (A) is
true, (B) is false.

(4) (A) is
false, (B) is true.

Answer: 2

62. Which
of the following pairs have different expressive power?

(1) Single-tape-turing
machine and multi-dimensional turing machine.

(2)
Multi-tape turing machine and multi-dimensional turing machine.

(3)
Deterministic push down automata and non-deterministic pushdown automata.

(4)
Deterministic finite automata and Non-deterministic finite automata.

Answer: 3

63. Which
of the following statements is false?

(1) Every
context-sensitive language is recursive.

(2) The set
of all languages that are not recursively enumerable is countable.

(3) The
family of recursively enumerable languages is closed under union.

(4) The
families of recursively enumerable and recursive languages are closed under
reversal.

Answer: 2

64. Let
C be a binary linear code with minimum distance 2t + 1 then it can correct upto
............bits of error.

(1) t + 1

(2) t

(3) t - 2

(4) t/2

Answer: 2

65. A
t-error correcting q-nary linear code must satisfy:

Where M is
the number of code words and X is

(1) q^{n}

(2) q^{t}

(3) q^{-n}

(4) q^{-t}

Answer: 1

66. Names
of some of the Operating Systems are given below:

(a) MS-DOS

(b) XENIX

(c) OS/2

In the above
list, following operating systems didn’t provide multiuser facility.

(1) (a) only

(2) (a) and
(b) only

(3) (b) and
(C) only

(4) (a), (b)
and (c)

Answer: Marks to all

67. From
the given data below:

a b b a a b b
a a b

which one of
the following is not a word in the dictionary created by LZ-coding (the initial
words are a, b)?

(1) a b

(2) b b

(3) b a

(4) b a a b

Answer: 4

68. With
respect to a loop in the transportation table, which one of the following is
not correct?

(1) Every loop
has an odd no. of cells and at least 5.

(2) Closed loops
may or may not b square in shape.

(3) All the cells
in the loop that have a plus or minus sign, except the starting cell, must be
occupied cells.

(4) Every
loop has an even no. of cells and at least four.

Answer: 1

69. At
which of the following stage(s), the degeneracy do not occur in transportation
problem?

(m, n
represents number of sources and destinations respectively)

(a) While
the values of dual variables u_{i} and v_{j} cannot be
computed.

(b) While
obtaining an initial solution, we may have less than m + n -1 allocations.

(c) At any
stage while moving towards optimal solution, when two or more occupied cells
with the same minimum allocation become unoccupied simultaneously.

(d) At a
stage when the no. of +ve allocation is exactly m + n - 1.

(1) (a), (b)
and (c)

(2) (a), (c)
and (d)

(3) (a) and
(d)

(4) (a), (b),
(c) and (d)

Answer: 3

70. Consider
the following LPP:

Min. Z = x_{1}+x_{2}+x_{3}

Subject to
3x_{1} + 4x_{3} ≤ 5

5x_{1 }+
x_{2} + 6x_{3} =7

8x_{1}
+ 9x_{3} ≥ 2

x_{1},
x_{2}, x_{3} ≥ 0

The standard
form of this LPP shall be:

(1) Min. Z =
x_{1 }+ x_{2} + x_{3} + 0x_{4} + 0x_{5}

Subject to
3x_{1} + 4x_{3} + x_{4} = 5;

5x_{1}
+ x_{2} + 6x_{3 }=7;

8x_{1 }+
9x_{3} - x_{5} = 2;

x_{1},
x_{2}, x_{3}, x_{4}, x_{5} ≥ 0

(2) Min. Z =
x_{1} + x_{2} + x_{3} + 0x_{4} + 0x_{5}
-1(x_{6})-1(x_{7})

Subject to
3x_{1} + 4x_{3} + x_{4} = 5;

5x_{1}
+ x_{2} + 6x_{3} +x_{6} = 7;

8x_{1}
+ 9x_{3} - x_{5} + x_{7} = 2;

x_{1}
to x_{7} ≥0

(3) Min. Z =
x_{1 }+ x_{2} + x_{3} + 0x_{4} + 0x_{5}
+ 0x_{6}

Subject to
3x_{1} + 4x_{3} + x_{4} = 5;

5x_{1}
+ x_{2} + 6x_{3} = 7;

8x_{1}
+ 9x_{3} - x_{5} + x_{6 }= 2;

x_{1}
to x_{6} ≥ 0

(4) Min. Z =
x_{1 }+ x_{2} + x_{3} + 0x_{4} + 0x_{5}
+ 0x_{6}+ 0x_{7}

Subject to
3x_{1} + 4x_{3} + x_{4} = 5;

5x_{1}
+ x_{2} + 6x_{3} + x_{6} = 7;

8x_{1}
+ 9x_{3} - x_{5} + x_{7} = 2;

x_{1}
to x_{7} ≥ 0

Answer: 1