Theory of Computer Science - Dec 2012

Computer Engineering (Semester 5)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks. 1(a) What is finite automation? Give the finite automation M accepting (a,b)(baaa).(5 marks) 1(b) Explain Chomsky Hierarchy with languages used, forms of productions in grammars and accepting device. (5 marks) 1(c ) Differentiate Moore and Mealy machine.(5 marks) 1(d) Give and explain ambiguous context free language.(5 marks) 2(a) Design finite state machine to add 2 binary numbers of equal length.(10 marks) 2(b) Give the rules for defining languages associated with any regular expression:Let, L1 = all words beginning with a L2 = all words ending with awhat is L1 intersection L2 ? (10 marks) 3(a) Give the statement for pumping Lemma for regular languages(2 marks) 3(b) Construct an NFA for
(i) (00 + 1) * (10)
(ii) ((0 + 1)* 10 + (00)(11 ))*(8 marks) 3(c) Let G be the grammar
S ? aB | bA
A ? a | aS | bAA
B ? b | bS | aBB
Find the leftmost derivation, right most derivation and parse tree for the string "bbaaabbaba".(10 marks) 4(a) What is TM? Give the power of TM over FSM. Explain undecidebility and incompleteness in Turing machine.(10 marks) 4(b) Explain PDA and power of PDM. Also design the NPDA for the given CFG:
S ? aAA
A ? bS
A ? aS
S ? a(10 marks) 5(a) Explain basic Complexity classes.(6 marks) 5(b) Define NP-hard and NP-complete languages.(4 marks) 5(c) Using pumping lemma, check whether aⁿbⁿ is regular or not.(10 marks) 6(a) How regular expression is converted to DFA? Explain all rules with example.(10 marks) 6(b) Construct a PDA accepting the language of Palindromes.(10 marks)

Write Short Notes on (any four) :-

7(a) Myhill Nerode Theorem(5 marks) 7(b) Universal TM(5 marks) 7(c) Rice Theorem(5 marks) 7(d) Closure property and decision algorithm for CFL.(5 marks) 7(e) Application areas of RE, FA,PDA, CFG,TM.(5 marks)