2001 QUESTIONS

CLICK ON A PICTURE BELOW FOR PREVIOUS GATE QUESTIONS 1987 ONWARDS IN THE THEORY OF COMPUTATION


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




SOLUTIONS TO GATE PROBLEMS 
SOLUTIONS TO GATE PROBLEMS 






GATE 2001 PROBLEMS

THEORY OF COMPUTATION



SECTION A

CS 1.4 Consider the following two statements:

S1: {0^2n|n>=1} is a regular language.

S2: {0^m1^n0^(m+n)|m>=1 and n>=1} is a regular language

Which of the following statements is correct?
A. Only S1 is  correct

B. Only S2 is correct

C. Both S1 and S2 are correct

D. None of S1 and S2 is correct

 

CS1.5 Which of the following statements is true?

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

B. The union of two context free languages is context free

C. The intersection of two context free languages is context free

D. The complement of a context free language is context free

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

A. N^2

B. 2^N

C.2N

D. N!

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

A. 8

B. 14

C. 15

D. 48

CS2.6 Consider the following languages:

L1 = {ww|w in {q,b}*}

L2 = {wwR| w in {a,b}*, wR is the reverse of w}

:3 = { 0^2i|i is an integer}

L4 = {0^i^2| i is an integer}

Which of the following languages are regular?

A. Only L1 and L2

B. Only L2, L3 and L4

Only L3 and L4

D. Only L3

CS2.7 Consider the following problem X.

Given a Turing machine M over the input alphabet X, any state q of M and a word w in X*, doe sthe computatio9n of M on w visit the state q?

Which of the following statements about X is correct?

A. X is decidable

B. X is undecidable but partially decidable

C. X is undecidable and not even partially decidable.

D. X is not a decision problem.

 


ANS
1987 1988 1989
1990 1991 1992
1993 1994 1995
1997 1998 1999
2000 2001 2002
2003 2004 1987
QUES
1987 1988 1989
1990 1991 1992
1993 1994 1995
1997 1998 1999
2000 2001 2002
2003 2004 1987
Go to:
2005,
GATE THEORY OF COMPUTATION

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