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

THEORY OF COMPUTATION



SECTION A

Q1.9 If the regular set A is represented by A=(01+1)* ant the regular set 'B' is represented by B= ((01)*1*)*, which of the following is true?

(a) A is a proper subset of B

(b) B is a proper subset of  A

(c) A and B are incomparable

(d) A=B

Q1.10 Which of the following sets can be recognized by a deterministic finite automaton?

(a) The numbers 1,2,4,8,----------.2^n,-------------written in binary.

(b) The umbrs 1.2.4.-------,2^n,--------------written in unary.

(c) The set of binary strings in which the number of zeros is the same as the number of ones.

(d) The st {1, 101, 11011, 1110111,--------}

Q1.11 Regarding the power of recognition of languages, which of the following statements is false?

(a) The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.

(b) Non-deterministic Push-down automata are equivalent to deterministic push-down automata.

(c) Non-deterministic Turing machines are equivalent to deterministic Turing machines.

(d) Multi-tape Turing machines are equivalent to single-tape Turing machines.

Q1.12 The string 1101 does not belong to the set represented by

(a) 110*(0+1)                    (b) 1(0+1)*101

(c) (10)*(01)*(00+11)*      (d) (00+(11)*0)*

Q2.5 Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite state automaton accepting L is

(a) 2         (b) 5        (c) 8        (d) 3

Q2.6 Which of the following statements is false?

(a) Every finite subset of a non-regular set is regular.

(b) Every subset of a regular set is regular.

(c) Every finite subset of a regular set is regular.

(d) The intersection of two regular sets is regular.

Q4. Design a deterministic finite state automaton (using the minimum number of states) that recognizes the following language:

L = {w in {0,1}*| w interpreted as a binary number (ignoring the leading 0's) is divisible by five}

SECTION B

Q13. Let M = ({q0,q1},{0,1},{z0,x},f,z0,0) be a pushdown automaton where f is given by

f(q0,1.z0) = {(q0,x,z0)}

f(q0,e,z0)  = {(q0,e)}

f(q0,1,X)  =  {(q0,XX)}

f(q1,1,X) = {(q1,e)}

f(q0,0,X) = {(q1,X)}
f(q1,0,z0) = {(q0,z0)}

(a) What is the language accepted by this PDA by empty store?

(b) Describe informally the working of the PDA?


Q14. Let G1 =(N,T,P,S1) be a CFG where,

N = {S1,A,B}            T= {a,b}

and P is given by

S1---------->a S1 b

S1-------->a Ab

A--------->aA

A-------->a

S1---->aBb

B---------->bB

B---------->b

What is L(G1)?

(b) Use the grammar in Part(a) to give a CFG for L2 =(a^ib^ja^kb^l|i,j,k,l>=1, i=j or k = l} by adding not more than 5 production rules.

(c) Is L2 inherently ambiguous?


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