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