Animation Calculator Calendar Charts Clocks
Colors Conversions Counters Dates FAQs
Finance Games Health Humour Internet
LiveConnect META Navigation Netscape 4 Others
Password Random Scrolls Search Sound
Validation VRML




Q12. Ram and Shyam have been asked to show that a certain problem II is NP-complete. Ram shows a polynomial time reduction frin tge 3-SAT problem to II, and Shyam shows a polynomial time reduction fro II to 3-SAT. Which of the following can be inferred from these reductions?

(a) II is NP-hard but not NP-complete

(b) II is is NP, but is not NP-complete

(c) II is NP-complete

(d) II is neither NP-hard. nor in NP

Q13. Nobody knows yet if P=NP. Consider the language L defined as follows:

L=(0+1)* if P=NP

L=null set otherwise

Which of the following statements is true?

(a) L is recursive

(b) L is recursively enumerable but not recursive

(c) L is not recursively enumerable

(d) Whether L is recursive or not will be known after we find out if P=NP

Q14. The regular expression  0*(10*)* denotes the same set as

(a) (1*0)*1*                (b) 0 + (0 +10)*

(c) (0+1)*10(0+1)*    (d) none of the above

Q15. If the strings of a language L can be effectively enumerated in lexicographic (i.e alphabetic) order, which of the following statements is true?

(a) L is necessarily finite

(b) L is regular but not necessarily finite

(c) L is context free but not necessarily regular

(d) L is recursive but not necessarily context free.

Q50. Consider the following deterministic finite state automaton M.



Let S denote the set of seven bit binary strings in which the first, the fourth and the last bits are 1. The number of strings in S that are accepted by M is

(a) 1            (b)5         (c) 7            (d) 8

Q51. Let G =({S},{a,b},R,S) be a context free grammar where the rule set R is


Which of the following statements is true?

(a) G is not ambiguous.

(b) There exist x, y in L(G) such that xy is not in L(G).

(c) There is a deterministic pushdown automaton that accepts L(G).

(d) We can find a deterministic finite state automaton that accepts L(G)

Q52. Consider two languages L1 and L2 each on the alphabet X. Let f:X--->X be a polynomial time computable bijection such that [for all x, x in L1 iff f(x) is in L2]. Further, let f^-1 be also polynomial time computable.

Which of the following CANNOT be true?

(a) L1 is in P and L2 is finite.

(b) L1 is in NP and L2 is in P.

(c) L1 is undecidable and L2 is decidable.

(d) L1 is recursively enumerable and L2 is recursive.

Q53. A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0,1,B} and its input alphabet is {0,1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table

  0 1 B
q0 q1, 1, R q1, 1, R Halt
q1 q1, 1, R q0, 1, L q0, B, L

The table is interpreted as illustrated below:

The entry (q1,1,R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes a 1 on the same tape square, moves its tape head one position to the right and transitions to state q1.

(a) M does not halt on any string in (0+1)+

(b) M does not halt on any string in(00+1)*

(c) M halts on all strings ending in a 0

(d) M halts on all strings ending in a 1

Q54. Define languages L0 andL1 as follows:

L0={<M,w,0>| M halts on w}

L1={<M,w,1>| M does not halt on w}

Here <M, w, i> is a triplet, whose first component, M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit.

Let L = L0 U L1. Which of the following is true?

(a) L is recursively enumerable, but L' is not.

(b) L' is recursively enumerable, but L is not

(c) Both L and L' are recursive

d) Neither L nor L' is recursively enumerable

Note:-L' is the complement of L

Q55. Consider the NFA M shown below:


Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

(a) L1 = {0,1}* - L            (b) L1 = {0,1}*

(c) L1 is a subset of L        (d) L1 = l


1987 1988 1989
1990 1991 1992
1993 1994 1995
1997 1998 1999
2000 2001 2002
2003 2004 1987
1987 1988 1989
1990 1991 1992
1993 1994 1995
1997 1998 1999
2000 2001 2002
2003 2004 1987
Go to:

CLICK!!! A remote control for GATE questions and answers!!