1987 ANSWERS

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 





Background:
Your Name:
Head Count:

Reload the page!!!

GATE-1987

GATE_1987-THEORY OF COMPUTATION QUESTIONS

HINTS AND SOLUTIONS

PART A



Q1(xii) ANSWER----(B)

If the grammar contains no useless nonterminals it is only part of the reduced grammar. So this excludes(A).

(B) is the definition of an ambiguous grammar.

(C) is excluded as any cfg in the chomsky normal form has two adjacent nonterminals.

Q1(xiii)ANSWER----(C)

If we are to consider all semantically correct programs then the class of context sensitive languages are sufficient to describe FORTRAN. The regular languages cannot do parenthesis matching ant the cfls cannot do type checking.

Q2(viii)ANSWER-----TRUE

The regular sets are closed under practically all operations. Consider the reversal of a regular expression to show the closure of the regular sets under reversal.

Q2(ix)ANSWER----FALSE

Any formal language is a subset of the set of all strings (which is regular). Thus the subsets of this regular set are an uncountable number wheras there are only a countably infinite number of regular sets.

Q2(x)ANSWER---FALSE

If we start with a minimised fa it is trivially a nfa, and in this case the nfa and dfa have the same number of states. The state explosion problem occurs in the worst case in the conversion of nfas to dfas.

Q2(xi)    ANSWER-----------FALSE

The cfls are not closed under intersection. Consider the intersection of the two cfls {an bn ci|i,n>1} and

{aj bm cm|j.m>1} which gives {ak bk ck|k>1} a standard csl which is not a cfl.

Q2(xii)     ANSWER--------TRUE

    If a set and its complement are r.e we merely need to run both the turing machines paralley.In a finite amount amount of time the membership problem can be solved, as one of the turing machines will halt.

Q2(xiii)    ANSWER-------------TRUE

This is a standard undecidable problem, which follows from the halting problem of turing machines.

PART B

Q10(c). This is the standard modulo 3 machine.

  input:1 output
q0 q1 nil
q1 q2 nil
q2 q0 1

Q10(d) The proper substrinfs of 0110 are

(0+01+011+1+11+110)



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