GATE 1988 QUESTIONS

THEORY OF COMPUTATION

Q2(viii) State the halting problem of Turing Machines.

Q2(ix) What is the type of the language L, where L = {a^n b^n | 0 < n <327the prime number}

Q15. Consider the DFA M and NFA M2 as defined in the figure below. Let the language accepted by the machine M be L.

What language does the machine M2 accept, if

(i) F2 = A?

(ii) F2 = B?

(iii) F2 = C?

(iv) F2 = D?

M = (Q,§,f,q0,F)

M2 = (Q2,§,f2,q00,F2)

where

Q2 = (QxQxQ) U {q00}

f2(q00,E)={<q0,q,q>| q e Q}

f2(<p,q,r>,a) = <f(p,a),f(q,a),r> for all p,q,r i Q and a in §

A = { <p,q,r>| p in  F; q, r in Q}

B = { <p,q,r>| p in  F; p, r in Q}

C  = { <p,q,r>| p, q, r in Q; there exists s in §* such that f(p,s) is in F)}

D = { <p,q,r>| p in  Q; q in F}

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