Theoretical Computer Science - Dec 2012

Computer Engineering (Semester 4)

TOTAL MARKS: 80
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if 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 a
what 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 anbn 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)