GATE 1994 PROBLEMS

THEORY OF COMPUTATION

SECTION A

Q1.16 Which of the following conversions is not possible (algorithmically)?

(A) Regular grammar to context-free grammar

(B) Non-deterministic FSA to deterministic FSA

(C) Non-deterministic PDA to deterministic PDA

(D) Non-deterministic Turing machine to deterministic Turing machine

Q2.10 The regular expression for the language recognized by the finite state automaton in the figure below is --------------------------------

Q3.3  State True or False with one line explanation:

A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).

SECTION B

Q19(a) Given a set S = {x | there is an x-block of 5's in the decimal expansion of pi}

(note: x-block is a maximal block of x successive 5's)

Which of the following statements is true with respect to S?

(i) S is regular

(ii) S is recursively enumerable

(iii) S is not recursively enumerable

(iv) S is recursive

Q19(b) Given that a language L1 is regular and that the language L1 U L2 is regular, is te language L2 always regular? Prove your answer.

Q20. A grammar G is in Chomsky-Normal form(CNF) if all its productions are of the form A---->BC or A--->a, where A,B and C are nonterminals and a is a terminal. Suppose G is a CFG in CNF and w is a string i L(G) of length l. How long is a derivation w in G?

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