CLICK ON A PICTURE BELOW FOR PREVIOUS GATE QUESTIONS 1987 ONWARDS IN THE THEORY OF COMPUTATION

 SOLUTIONS TO GATE PROBLEMS
 SOLUTIONS TO GATE PROBLEMS

GATE-1987

GATE_1987-THEORY OF COMPUTATION QUESTIONS

HINTS AND SOLUTIONS

PART A

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.

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.

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.

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.

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.

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.

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.

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