RGPV BHOPAL,MP
M.C.A.(3RD Semester) Examination
THEORY OF COMPUTATION [MCA-304]
Time: 3 Hrs Max Marks: 100 Min: 40
Note :Attempts All questions.All Question carry equal marks.
Note :Attempts All questions.All Question carry equal marks.
UNIT-I
Q.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 :OR
Q.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
Q.3.(a) Explain Chomsky classification of languages with suitable examples.?(b) Construct a regular expression corresponding to the state diagram given as :
Q.4.(a) Construct a regular grammar G generating the regular set represented by :
P = a*b(a+b)*
(b) Show the auto mata M1 and M2 given in figures are equivalent.
(c) State application of the pumping lemma
UNIT-III
Q.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}.
OR
Q.6.(a) Find a context-free 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 context-free :
L = {w1 ? w2 : w1,w2 ? {a,b}*,w1 ? w2}
UNIT-IV
Q.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 ?
OR
Q.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
Q.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 context-sensitive language L not including ?, there exists some linear bounded
automation M such that L = L(M).
OR
Q.10.(a) Prove that every context-sensitive language L is recursive.?(b) Determine whether or not the following statement is true :
"Any problem whose domain is finite is decidable."
META TAGS:-RGTU MCA 3RD SEM OLD PAPERS I RGTU THEORY OF COMPUTATION PREVIOUS PAPERS I RGPV THEORY OF COMPUTATION SAMPLE PAPERS I RGTU MCA-304 TOC SAMPLE PAPERS I RGPV THEORY OF COMPUTATION GUESSING PAPERS I RGPV MCA-304 THEORY OF COMPUTATION GUESS PAPERS I RGPV MCA-304 TOC QUESTION PAPERS I RGTU MCA-304 EXAM PAPERS I RGTU THEORY OF COMPUTATION MODEL PAPERS I RGPV MCA-304 TOC QUESTION PAPERS I RGTU THEORY OF COMPUTATION TEST PAPERS I RGPV MCA-304 LAST 5 YEAR TOC PAPERS I RGPV MCA-304 PAST YEAR PAPERS I RGPV TOC MODEL TEST PAPERS I RGPV MCA 3RD SEM ALL PAPERS I RGTU MCA 3RD SEM ALL SUBJECT PAPERS I
