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