THEORY OF COMPUTER SCIENCE (TCS) DECEMBER 2010 COMPUTER SCIENCE SEMESTER 5
Con. 5564-10. (REVISED COURSE) GT-6708.(3 Hours) [Total Marks:100]
N.B.: (1) Question No.1 is compulsory.
(2) Attempt any four questions from remaining six questions.
(3) Draw suitable diagrams wherever necessary.
(4) Assume suitable data, if necessary.
Q.1 (a) Explain different types of machines and states at least one application of each. [10 Marks]
(b) Let G be the grammar. Find the leftmost derivation, rightmost derivation and parse tree for
the string 00110101 [10 Marks]
G: S -> 0B|1A
A -> 0|0S|1AA
B -> 1|1S|0BB
Q.2 (a) Design a DFA to accept [10 Marks]
(i) a set of all strings with odd number of ones followed b even number of zeros.
(ii) a set of all strings with which begin and end with different letters ∑= {x,y,z}
(b) What is a regular expression? Give formal definition of a regular expression. Design a
DFA corresponding to the regular expression (a+b) * aba(a+b)*. [10 Marks]
Q.3 (a) Design a Moore and Mealy machine to convert each occurrence of a substring abb by
aba. [10 Marks]
(b) Convert the following NFA with epsilon moves to an NFA without epsilon moves and then
to a DFA. [10 Marks]
(i)
(ii)
(b) Design a turing machine to generate the languages given by a regular expression
0(0+1)*11. [10 Marks]
Q.5 (a) List and explain decision properties of regular languages. Explain the test for checking
emptiness of a regular language. [10 Marks]
(b) State Arden's theorem and use it to construct a regular expression correspondence to the
following automata. [10 Marks]
S -> bA|aB
A -> bAA |aS|a
B -> aBB|bS|b
(ii) Construct a PDA accepting the following language
(b) Explain the rules for simplification of a context free grammar. [10 Marks]
Q.7 Write short notes on(any three):- [20 Marks]
(a) Variants of a Turing Machine
(b) Post Correspondence Problem
(c) Chomsky Hierarchy
(d) Intractable Problem
(e) Recursive and recursively enumerable languages.
No comments:
Post a Comment