GATE 2000 PROBLEMS

THEORY OF COMPUTATION

SECTION A

Q(1.4) Let S and T be languages over X={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

A. S is a proper subset of T

B. T is a proper subset of S

C. S = T

D. S intersection T = empty set

Q(1.5) Let L denote the language generated by the grammar S----->0S0|00. Which of the following is true?

A. L = 0+

B. L is regular but not 0+

C. L is context free but not regular

D. L is not context-free

Q(2.8) What can be said about a regular language L over {a} whose minimal finite state automaton has two states?

A. L must be {a^n|n is odd}

B. L must be {a^n| n is even}

C. L must be {a^n|n>= 0}

D. Eother L must be {a^n|n is odd}, or L must be {a^n|n is even}

Q(2.9) Consider the following decision problems:

(P1) Does a given finite state machine accept a given string.

(P2) Does a given context free grammar generate an infinite number of strings.

Which of the following is true?

A. Both (P1) and (P2) are decidable.

B.Neither (P1) nor (P2) is decidable

C. Only (P1) is decidable

D. Only (P2) is decidable

SECTION B

CS7 (a) Construct a minimal finite state machine that accepts the language over{0,1}, of all strings that contain neither the substring 00 nor the substrng 11.

CS7(b) Consider the grammar

S----------------->aSAb

S------------->e

A--------------->bA

A--------------->e

where S, A are non-terminal symbols with S being the start symbol; a, b are terminal symbols and e is the empty string. This grammar generates strings of the form a^ib^j for some i,j>=0, where i and j satisfy some condition. What is the condition on the values of i and j?

CS8. A push down automaton (pda) is given in the following extended notation of finite state diagrams:

The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the for d, s/s' where d is the ilnput symbol read and s, s' are the stack contents before and after the move. For example, the edge labeled , s/1.s denotes the move from state q0 to q0 in which the input symbol 1 is read and pushed to the stack.

(a) Introduce two edges with appropriate labels in the above diagram so that the resulting pda accepts thelanguage

{x2xR|x in {0,1}*, xR denotes reverse of x},

by empty stack

(b) Describe a nondeterministic pda with three states in the above notation that accepts the language {0^n1^m|n <= m <= 2n} by empty stack.

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