a knowledge trading engine...

Rajiv Gandhi Proudyogiki Vishwavidyalaya 2008-3rd Sem M.C.A Computer Aplications .(ester) ,e, - Question Paper

Monday, 28 January 2013 10:35Web

Page 1 of 7

MCA-304(N)
M.C.A.(Third Semester) EXAMINATION,June,2008
(New Course)
THEORY OF calculation
[MCA-304(N)]
Time : 3 Hours
Maximum Marks :100
Minimum Pass Marks : 40

Note : Attempt 1 ques. from every Unit. All ques. carry equal marks.

Unit - I
1.(a) Construct a minimum state automation equivalent to provided automata A, whose transition graph
is as :

(b) Construct an NFA equivalent to the two DFA :
({q0,q1,q2},{0,1},d,{q0{,{q1}) where d is provided as :

2.(a) Consider the subsequent ?-NFA :

(i) calculate the ?-closure of every state.
(ii) provide all the strings of length 3 or less accepted by the automaton.
(iii) Convert the automaton to a DFA.
(b) provide DFS's accepting the subsequent 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) discuss Chomsky classification of languages with suitable examples.
(b) Construct a regular expression corresponding to the state diagram provided 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 provided 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) obtain 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 situation free languages is not closed under intersection.
(c) Determine whether or not the subsequent language is context-free :
L = {w1 ? w2 : w1,w2 ? {a,b}*,w1 ? w2}

Unit - IV
7.(a) Construct a turing machine to calculate 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 various
from the one. It reads, that is, if :
d(qi,a) = (qj,b, L or R)
then a and b must be various. Does this limitation decrease the power of the automation ?
8.(a) provided 2 positive integers x and y, design a turing machine as transducers that computes
x + y.
(b) explain 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 2 turing machines M1 and M2 accept the
identical language.
(b) For every context-sensitive language L not including ?, there exists a few 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 subsequent statement is actual :
"Any issue whose domain is finite is decidable."