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

THEORY OF COMPUTATION



SECTION A

Q3.4 Give X={a,b}, which of the following sets is not countable?

(A) Set of all strings over X

(B) Set of all languages over X

(C) Set of all regular languages over X

(D) Set of all languages over X accepted by Turing machines

Q6.4 Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?

(A) 0*(1+0)*        (B)0*1010*        (C) 0*1*01        (D) 0*(10+1)*

Q6.5 Which one of the following is not decidable?

(A) Given a turing machine M, a string s and an integer k, M accepts s within k steps

(B) Equivalence of two given turing machines

(C) Language accepted by a given finite state machine is non-empty.

(D) Language generated by a context-free grammar is non-empty.

Q6.6 Which of the following languages over {a,b,c} is accepted by a deterministic push down automaton?

(A) {wcwR| w in(1+b)*}
(B) {wwR|w in {a,b,c}*}

(C){a^n b^n c^n|n>=0}

(D) { w| w is a palidrome over {a,b,c}

Note:- wR is obtained by reversing the string "w".

Q11. Consider the grammar

S---------------->bSe

S--------------->PQR

P----------------->bPc

P------------->epsilon

Q----------->cQd

Q--------->epsilon

R---------->dRe

R---------->epsilon

where  S,P,Q,R are non-terminals with S being the start symbol; bc,c,d,e are terminal symbols and "epsilon" is the empty string. This grammar generates strings of the form b^i c^j d^k e^m for some i, j,k, m <=0.

(a) what is the condition on the values of u, j, k ,m?

(b) Find the smallest string that has two parse trees.

SECTION B

Q20. Construct a finite state machine with minimum number of states, accepting all strings over {a,b} such that the number of a's is divisible by two and the number of b's is divisible by three.

Q21. Given that L is a language accepted by a finite state machine, show that Lp and Lr are accepted by some finite state machines where

Lp ={s|ss"in L for some string s"},

Lr={s|s obtained by reversing some string in L}


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