Andhra University 2005 M.C.A 2.1.1 THEORY OF COMPUTATION - Question Paper

2004-05 MODEL PAPER

MCA 2.1.1

THEORY OF calculation

First ques. is Compulsory

ans any 4 from the remaining

ans all parts of any ques. at 1 place.

Time: three Hrs.
Max. Marks: 100

1. a). Let S={a,b}. Write regular expression for the set of all strings in S* with no more than 3 a’s.
b). State the mathematical definition of DFA.
c). describe situation 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 issue.
h). describe the class NP.
i). describe the concept of validity in prepositional calculus.
j). Construct truth tables for the subsequent 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 provided beneath :
-----DIAGRAM-----

3. a). Show that the class of Languages accepted by pushdown automata is exactly the class of context-free languages.
b). Construct situation free Grammar that generate the language
{wcwR ? we {a, b}*}

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

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

6. a). What is halting problem? discuss
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 e P.
b). Show that Travelling salesman issue is NP-complete.

8. a). Show that the subsequent formula of prepositional calculus is a Tautology.
(( P?Q) ?R))?((P?Q) ?(P?R))
b). define resolution in Predicate calculus.

Earning:   Approval pending.