GATE 1987 QUESTIONS

THEORY OF COMPUTATION

PART A

Q1(xii) A context free grammar is ambiguous is:

(A) The grammar contains useless non-terminals.

(B) It produces more than one parse tree for some sentence.

(C) Some production has two non-terminals side by side on the right-hand side.

(D) None of the above.

Q1(xiii) FORTRAN is a:

(A) Regular language                    (B) Context-free language

(C) Context-sensitive language     (D) None of the above

PART B

Q10(c) Give the minimal DFA that performs as a mod-3 1's counter, i.e. outputs a 1 each time the number of 1's in the input sequence is a multiple of 3.

Q10(d) Give regular expression over the alphabet {0,1} to denote the set of proper non-null substrings of the string 0110.

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