GATE 2003

THEORY OF COMPUTATION

HINTS AND SOLUTIONS TO PROBLEMS

Q12. ANSWER--------------------(C)

3-SAT is a standard NP-complete problem so both the problems are NP-complete.

Q13. ANSWER---------------(A)

(0+1)* is a regular set and hence it is recursive, the null set is recursive. Hence whether P= NP or not both choices yield recursive as the answer.

Q14. ANSWER----------(A)

e (the empty string) is cumpulosily in 0*(10*)* and this excludes (B) and (C) as the answers. ). 0*(10*)* is the same as (0+1)* and this is the same as 1*(01*)*. Any string in (0+1)* can be considered to optionally start with a 0, contain sequences of 0's separted by a 1 or we can consider any string in (0+1)* to start optionally with some 1's and followed by seuences of 1's separated by 0's.

Q15. ANSWER-------------(D)

It is a standard theorem that if we can lexicographically enumerate a r.e. set then the set is recursive. To check if a string is in the r.e. set we enumerate strings till we get some string of longer length accepted, then we can decide the membership problem.

Q50. ANSWER-------(C)

Name the states of the finite automata left to right as A,B,C and D.

The strings with the 1st, fourth and seventh bits as 1's will be

1001D001

1001D011

1001D101

1001D111

1011A001

1011A011

1011A101

1011A111

1101A001

1101A011

1101A101

1101A111

1111A001

1111A010

1111A101

1111A111

The first fout are aceepted. In the remaining three block of fours only the first string is accepted.

Q51. ANSWER---------(C)

e (the empty string) has an infinite number of derivation trees and this excludes (A). We can rewrite the grammar as S--------->(S)|SS|e and thus the language generated is nothing but the set of all balanced parentheses. Parenthesis matching cannot be done by a finite automata and this excludes (C). The concatentation of any two strings of balanced parenthesis is a balanced parenthesis string and this excludes (B). Parentheses mathcing can be done by a dpda and hence ( C) is the answer.

Q52.ANSWER---------------(C)

To see a simple solution let us take the special case of L1=L2=L.

(A) It is possible now that L2 is finite and L1 is trivially in P, as every finite set is in P.

(B) L2 in P means L1 can be in NP as every language in P is trivially in NP.

(D) L2 is recursive and L1 in r.e. sets is possible as every recursive set is trivially r.e.

So by elimination we have (C) as the answer. Evidently if L1 is undecidable then then it cannot be recursive like L2.

Q53. ANSWER---------(A)

Let us eliminate the cases.

Consider the machine on blank tape then e is the input. On a B the machine halts. This excludes (B).

It is easy to check that the machine loops on inputs 0 and 1.

Thus (A) is the answer.

Q54. ANSWER-------------(D)

If L is r.e. then we have a turing machine M accepting it. Let M be an enumerator(any turing machine can be considered to be an enumerator). Then for any Turing Machine M' and input w' in  a finite amount of time M will enumerate the string <M',w',0> or <M',w',1> thus deciding if M' on input w' halts or not. Such a machine cannot exist.

Consider the complement of L=L', accepted by a turning machine M1. If a machine M1 exists then it will enumerate either <M',w',0> or <M',w',1> in a finite amount of time resolving the halting problem. So L'  cannot be r.e.

 Q55. ANSWER-------(B)

By interchanging the final and nonfinal states of M we see that the new machine gives e as an element of L1 as the start state becomes a final state in the machine for L1. This excludes (C) and (D) from the answers. 1 is in L and L1 and this excludes (A) from the answer.The only choice left is (B).

In the machine for L1 we have a complete finite automata where all the states i.e entries in the transititon table are final states. Thus l1 is (0+1)*.

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