Rajiv Gandhi Proudyogiki Vishwavidyalaya(Technical University) Computer M.C.A.(Third Semester) EXAMINATION,June,2008 model question papers

Posted Date: 09 Jul 2009      Posted By:: rajesh kale    Member Level: Silver  Points: 5 (₹ 1)

2008 Rajiv Gandhi Proudyogiki Vishwavidyalaya(Technical University) Computer M.C.A M.C.A.(Third Semester) EXAMINATION,June,2008 Question paper

 Course: M.C.A University/board: Rajiv Gandhi Proudyogiki Vishwavidyalaya(Technical University)

MCA-304(N)
M.C.A.(Third Semester) EXAMINATION,June,2008
(New Course)
THEORY OF COMPUTATION
[MCA-304(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 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
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 context-sensitive language L not including ?, there exists some linear bounded
automation M such that L = L(M).

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."

Related Question Papers:

• M.C.A.(Third Semester) EXAMINATION,Dec.,2008

• M.C.A.(Third Semester) EXAMINATION,June,2008

• M.C.A.(Fourth Semester) EXAMINATION,Dec.,2008

• M.C.A.(Second Semester) EXAMINATION, June,2007

• M.C.A.(Second Semester) EXAMINATION, June,2007

• Categories

Submit Previous Years University Question Papers and make money from adsense revenue sharing program

Are you preparing for a university examination? Download model question papers and practise before you write the exam.

Looking for University or College admissions in India for 2021 - 2022 Academic Year?

Top Contributors
TodayLast 7 Daysmore... 