2008 Rajiv Gandhi Proudyogiki Vishwavidyalaya(Technical University) Computer M.C.A M.C.A.(Third Semester) EXAMINATION,June,2008 Question paper
MCA304(N) M.C.A.(Third Semester) EXAMINATION,June,2008 (New Course) THEORY OF COMPUTATION [MCA304(N)] Time : Three Hours Maximum Marks :100 Minimum Pass Marks : 40
Note : Attempt one question from each Unit. All questions carry equal marks.
Unit  I 1.(a) Construct a minimum state automation equivalent to given automata A, whose transition graph is as :
(b) Construct an NFA equivalent to the 2 DFA : ({q0,q1,q2},{0,1},d,{q0{,{q1}) where d is given as :
2.(a) Consider the following ?NFA :
(i) Compute the ?closure of each state. (ii) Give all the strings of length three or less accepted by the automaton. (iii) Convert the automaton to a DFA. (b) Give DFS's accepting the following languages over the alphabet {0,1} : (i) The set of all strings beginning with a 1, when interpreted as a binary integer, is a multiple of 5. (ii) The set of all strings that, when interpreted in reverse as a binary integer, is divisible by 5.
Unit  II 3.(a) Explain Chomsky classification of languages with suitable examples. (b) Construct a regular expression corresponding to the state diagram given as : 4.(a) Construct a regular grammer G generating the regular set represented by : P = a*b(a+b)* (b) Show the automata M1 and M2 given in figures are equivalent. (c) State application of the pumping lemma Unit  III 5.(a) Convert the Grammer : S > AB/aB A > aab/? B > bbA into Chomsky normal form.
(b) Construct npda's that accept the language : L = {an bm : n <=m<=3n} on S = {a,b}. 6.(a) Find a contextfree grammar that generates the language accepted by the npda : M = ({q0,q1},{a,b},{A,z},d,q0,z,{q1}) with transitions : d(q0,a,z) = {(q0,Az)} d(q0,b,A) = {(q0,AA)} d(q0,a,A} = {(q1,?)} (b) Show that the family of unambiguous context free languages is not closed under intersection. (c) Determine whether or not the following language is contextfree : L = {w1 ? w2 : w1,w2 ? {a,b}*,w1 ? w2}
Unit  IV 7.(a) Construct a turing machine to compute the function f(w) = wr,where w ? {1,0}+. (b) Show that the Cartesian product of a finite number of countable sets is countable. (c) Suppose we make the restriction that a turing machine must always write a symbol different from the one. It reads, that is, if : d(qi,a) = (qj,b, L or R) then a and b must be different. Does this limitation reduce the power of the automation ? 8.(a) Given two positive integers x and y, design a turing machine as transducers that computes x + y. (b) Discuss Linear Bounded Automata. Show that the class of turing machine with multitape is equivalent to the class of standard turing machine.
Unit  V 9.(a) Show that there is no algorithm for deciding if any two turing machines M1 and M2 accept the same language. (b) For every contextsensitive language L not including ?, there exists some linear bounded automation M such that L = L(M).
10.(a) Prove that every contextsensitive language L is recursive. (b) Determine whether or not the following statement is true : "Any problem whose domain is finite is decidable."
Attachments:
Return to question paper search
