Theoretical Computer Science - May 2015

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) Differentiate between NFA and DFA.(5 marks) 1 (b) State and Explain closure properties of Context Free Language.(5 marks) 1 (c) Explain with an example the Chomsky hierarchy.(5 marks) 1 (d) Compare recursive and recursively enumerable language.(5 marks) 2 (a) Construct PDA accepting the language L={aⁿbⁿ |n>0}.(10 marks) 2 (b) Design minimized DFA for accepting strings ending with 100 over alphabet (0,1).(10 marks) 3 (a) Convert (0+ε)(10)*(ε+1) into NFA with e-moves and obtains DFA.(10 marks) 3 (b) Construct Turing machine that accepts the string over ?=(0,1) and convert every occurrence of 111 to 101.(10 marks) 4 (a) Convert following Grammar to CNF and GNF
S→ASB/a/bb
A→aSA/a
B→Sbs/bb(10 marks) 5 (a) Design Moore Machine to generate output A if string is ending with abb, B if string ending with aba and C otherwise over alphabet (a,b) and convert it to Mealy machine.(10 marks) 5 (b) Construct TM to check wellformed ness of parenthesis.(10 marks)

Write short notes on:

6 (a) Rice theorem(5 marks) 6 (b) Variants of Turing Machine.(5 marks) 6 (c) Applications of Regular Expression(5 marks) 6 (d) Difference between PDA and NPDA(5 marks)