2004-05 MODEL PAPER

MCA 2.1.1

THEORY OF COMPUTATION

First Question is Compulsory

Answer any four from the remaining

Answer all parts of any Question at one place.

Time: 3 Hrs.
Max. Marks: 100

1. a). Let Σ={a,b}. Write regular expression for the set of all strings in Σ* with no more than three a’s.
b). State the mathematical definition of DFA.
c). Define Context Free grammar.
d). What is configuration of a Turing machine?
e). When do we say that a function is Turing – computable.
f). When do we say that a function is Primitive recursive?
g). State post correspondence problem.
h). Define the class NP.
i). Define the concept of validity in prepositional calculus.
j). Construct truth tables for the following formula : (A ↔ (B ↔ A))

2. a). Prove that, for every non deterministic finite automation there is an equivalent deterministic finite automation.
b). Construct DFA equivalent to non-deterministic automata given below :
-----DIAGRAM-----

3. a). Show that the class of Languages accepted by pushdown automata is exactly the class of context-free languages.
b). Construct context free Grammar that generate the language
{wcw^R ⌈ wε {a, b}*}

4. a). Describe the Turing Machine which shifts a string w containing no blanks to one cell to the left.
b). Construct a Turing Machine that accepts the Languages a^* ba^*b.

5. a). Describe the method of Godelization
b). Show that the function f(n) = n! is primitive recursive

6. a). What is halting problem? Explain
b). Show that any finite set is Turing-decidable

7. a). Let L b an NP-complete language. Then P=NP if and only if L ε P.
b). Show that Travelling salesman problem is NP-complete.

8. a). Show that the following formula of prepositional calculus is a Tautology.
(( P→Q) →R))→((P→Q) →(P→R))
b). Describe resolution in Predicate calculus.