2000 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 2000 PROBLEMS

THEORY OF COMPUTATION



SECTION A

Q(1.4) Let S and T be languages over X={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

A. S is a proper subset of T

B. T is a proper subset of S

C. S = T

D. S intersection T = empty set

Q(1.5) Let L denote the language generated by the grammar S----->0S0|00. Which of the following is true?

A. L = 0+

B. L is regular but not 0+

C. L is context free but not regular

D. L is not context-free

Q(2.8) What can be said about a regular language L over {a} whose minimal finite state automaton has two states?

A. L must be {a^n|n is odd}

B. L must be {a^n| n is even}

C. L must be {a^n|n>= 0}

D. Eother L must be {a^n|n is odd}, or L must be {a^n|n is even}

Q(2.9) Consider the following decision problems:

(P1) Does a given finite state machine accept a given string.

(P2) Does a given context free grammar generate an infinite number of strings.

Which of the following is true?

A. Both (P1) and (P2) are decidable.

B.Neither (P1) nor (P2) is decidable

C. Only (P1) is decidable

D. Only (P2) is decidable

SECTION B

CS7 (a) Construct a minimal finite state machine that accepts the language over{0,1}, of all strings that contain neither the substring 00 nor the substrng 11.

CS7(b) Consider the grammar

S----------------->aSAb

S------------->e

A--------------->bA

A--------------->e

where S, A are non-terminal symbols with S being the start symbol; a, b are terminal symbols and e is the empty string. This grammar generates strings of the form a^ib^j for some i,j>=0, where i and j satisfy some condition. What is the condition on the values of i and j?

CS8. A push down automaton (pda) is given in the following extended notation of finite state diagrams:

 

 

 

The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the for d, s/s' where d is the ilnput symbol read and s, s' are the stack contents before and after the move. For example, the edge labeled , s/1.s denotes the move from state q0 to q0 in which the input symbol 1 is read and pushed to the stack.

(a) Introduce two edges with appropriate labels in the above diagram so that the resulting pda accepts thelanguage

{x2xR|x in {0,1}*, xR denotes reverse of x},

by empty stack

(b) Describe a nondeterministic pda with three states in the above notation that accepts the language {0^n1^m|n <= m <= 2n} by empty stack.


 

 

 

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!!