Centre for Development of Advanced Computing(C-DAC) 2006 M.C.A -104 Theory of Computation - Question Paper

End-Term exam
Second Semester [MCA] – MAY-JUNE 2006

MCA-104 Theory of calculation
Time: three Hours Maximum Marks: 60

Q. 1
(a) Draw a finite automata that accepts sets of strings composed of zeros and ones
which end with string 00.
(b) describe an inherently ambiguous language. provide an example of such language.
(c) provide a recursive formula for addition of 2 positive numbers using initial
functions like zero, identify and successor functions. Hence show that addition of
two positive numbers is computable.
(d) Show that if M1 is a Moore machine then their exists a corresponding Mealy
machine.
(e) Draw a NFA with 3 states that accepts L= {a^n : n >= 1} U {b^k a^m : k >= 0 m >= 0}.
(4 x five = 20)

Q. 2
(a) Show that the set of all strings in {0, 1} such that every 3rd symbol is the identical
as the 1st symbol is a regular language.
(b) Construct a situation free grammar for the language L={w | w # {0, 1}* , | w | is
odd and w contains 0 in the middle of the string}.
(5, 5)

Q. three Convert the subsequent situation Free Grammar into GNF.
S ~> bA
S ~>aB
A ~>bAA
A ~>aS
A ~>a
B ~>aBB
B ~>bS
B ~>b’

Q. 4
(a) Draw a Push Down Automata with minimum number of pushdown stores of the
language {wcwR | w # {0, 1}*}. Here wR is reverse string of w.
(b) provide a matrix grammar for the above language. (7, 3)

Q. 5
(a) describe a Turing machine. Draw a Turing Machine that adds 2 positive integers.
(b) State and prove the pumping lemma for CFL. (5, 5)

Q. 6
(a) describe Derivation Tree. Is it possible to draw a derivation tree for a string derived
from situation sensitive grammar? provide reasons for your ans. (5, 5)
(b) Let ‘10011010011’ is a symbol sequence. Apply the subsequent prioritized Markov
rules to convert the sequence such that all symbols subsequent the trend ‘1101’
should be ‘0’.
(1) a0 ~> 0a
(2) a1 ~> 0a
(3) a ~>
(4) 1101 ~> 1101a
(5) ~>

Q. seven Write short notes on any 2 of the following:- (5, 5)
(a) L –System of grammar
(b) Partial recursive function
(c) Unsolvable class or issue.

Earning:   Approval pending.