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.

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