GATE 1991 PROBLEMS

THEORY OF COMPUTATION

PART A

Q3(xiii) Let r = 1(1+0)*, s = 11*0, t = 1*0 be three regular expressions. Which one of the following is true?

(A)L(s) is a subset of L(r) and L(s) is a subset of L(t)

(B) L(r) is a subset of L(s) and L(s) is a subset of L(t)

(C) L(s) is a subset of L(t) and L(s) is a subset of L(r)

(D) L(t) is a subset of L(s) and L(s) is a subset of L(r)

Q3(xiv) Which one of the following is the strongest correct statement about a finite language over some finite alphabet X?

(A) It could be undecidable.

(B) It is Turing machine recognizable

(C) It is a regular language

(D) None of the above

PART B

Q17(a)  Show that Turing machines, which have a read only input tape and a constant work size tape, recognize precisely the class of regular languages.

Q17(b) Let L be the language of all binary strings in which the third symbol from the right is a 1. Give a non-deterministic finite automaton that recognizes L. How many states does the minimised equivalent deterministic finite automaton have? Justify your answer briefly.

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