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


GATE1987
GATE_1987THEORY 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)ANSWERTRUE
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)ANSWERFALSE
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)ANSWERFALSE
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) ANSWERFALSE
The cfls are not closed under intersection. Consider the intersection of the two cfls {an bn cii,n>1} and
{aj bm cmj.m>1} which gives {ak bk ckk>1} a standard csl which is not a cfl.
Q2(xii) ANSWERTRUE
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) ANSWERTRUE
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 