GATE 1996 PROBLEMS

THEORY OF COMPUTATION

SECTION A

Q1.8 Two of the following four regular expressions are equivalent which two? (e is the empty string).

(i) (00)*(e+0)    (ii) (00)*    (iii) 0*    (iv) 0(00)*

(A) (i) and (ii)    (B) (ii) and (iii)    (C) (i) and (iii)    (D) (iii) and (iv)

Q1.9 Which of the following statements is false?

(A) The Halting problem of Turing machines is undecidable.

(B) Determining whether a context free grammar is ambiguous  is undecidable.

(C) Given two arbitrary context free grammars G1 and G2 it is undecidable whether L(G1)=L(G2).

(D) Given two regular grammars G1 and G2 it is undecidable whether L(G1)=L(G2).

Q1.10 Let L be a subset of X* where X={a,b}. Which of the following is true?

(A) L = {x| x has an equal number of a's and b's} is regular.

(B) L = {a^n b^n| n>=1} is regular.

(C) L = {x | x has mores a's than b's} is regular.

(D) L = {a^m b^n | m>=1, n>=1} is regular

Q2.8 If L1 and L2 are context free languages and R a regular set, one of the languages below is not necessarily a context-free language. Which one?

(A) L1L2   (B) L1 intersection L2  (C) L1 intersection R  (D) L1 U L2

Q2.9 Define for a context-free language L over {0,1}, init(L)={u|uv in L for some v in {0,1}*}, in other words init(L) is the set of prefixes of L.

Let L= {w|w is nonempty and has an equal number of 0.s and 1's}

Then init(L) is

(A) the set of all binary strings with an unequal number of 0's and 1's

(B) the set of all binary strings including the null string

(C) the set of all binary strings with exactly one more 0's than the number of 1's or one more 1 then the number of 0's.

(D) None of the above

SECTION B

Q11. Let G be a context-free grammar where G= ({S,AB,C},{a,b,d},P,S} with the productions in P given below.

S-------------->ABAC

S--------------->aA|e

S--------------->bB|e

C--------->d

(e denotes the null string).

Transform the grammar G to an equivalent context-free grammar that has no e-productions and no unit productions. ( A unit production is of the form x----->y, where x and y are nonterminals).

Q12. Given below are the transiton diagrams for two finite state machines M1 andM2 recognising languages L1 and L2 respectively.

(a) Display the transition diagram for a machine that recognizes L1L2 obtained from transition diagrams for M1 and M2 by adding only & transitions and no new states.

(b) Modify the transition diagram obtained in part (a) to obtain a transition diagram for a maachie that recognizes (L1L2) by adding only e transitions and no new states.

(Final states are enclosed in double circles).

Q13. Let Q = ({q1,q2},{a,b},{a,b,Z},f,{q1,q2},Z,0) be a push down automaton accepting by empty stack the language which is the set of all nonempty even palidromes over the set {a,b}. Below is an incomplete specification of the transitions for Q. Complete the specification. The top of the stack is assumed to be at the right end of the string representing the stack contents.

(1) f(q1,a,Z) = {(q1,Za)}

(2) f(q1,b,Z) = {(q1,Z)}

(3) f(q1,a,a)= {-----------,-----------}

(4) f(q1,b,b)={----------,------------}

(5) f(q2,a,a)={(q2,e)}

(6) f(q2,b,b)={(q2,e)}
(7) f(q2,e,Z)={(q2,e)}

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