Theoretical Computer Science - May 2013

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) Define the following terms:
(i) Undecidability
(ii) Unrestricted Grammer
(iii) Pumping Lemma(5 marks) 1 (b) Define TM and give its variants. (5 marks) 1 (c) Explain Chomsky hierarchy for formal languages.(5 marks) 1 (d) Give the closure properties of regular languages.(5 marks) 2 (a) (i) What is ambiguous CFG? Give one example.
(ii) What is Myhill-Nerode theorem? Explain necessity of it.(10 marks) 2 (b) Let G be the grammar, find the leftmost derivation, rightmost derivation and parse tree for the string 00110101
S → 0B/1A
A → 0/0S/1AA
B → 1/1S/0BB(10 marks) 3 (a) Explain CNF and GNF with example.(10 marks) 3 (b) Give the formal definition of RE and Design DFA corresponding the regular expression (a+b)aba( a + b )(5 marks) 3 (c) Using pumping lemma prove L = {anbn | n?1} is not regular or not.(5 marks) 4 (a) Write NFA for accepting (a+bb)(ba+ ∈)(10 marks) 4 (b) Explain DPDA and NPDA with languages of them. (10 marks) 5 (a) Find the languages defined by the following grammar:
(i) S→OA/IC
A→OS/IB/∈
B→1A/OC
C→OB/1S
(ii) S→OA/IC
A→OS/IB
B→OC/IB/∈
C→OB/IS(10 marks) 5 (b) Construct PDA of accepting the following language L = {aⁿb^maⁿ | m,n>=1}(10 marks) 6 (a) Differentiate between Moore and Mealy machine with proper example and usage. Carry out comparison of Moore MIC to Mealy MIC.(10 marks) 6 (b) Design a Turing Machine to accept the language L = {aⁿ bⁿ | n>=1}(10 marks)

Write short notes on (any four)

7 (a) Recursive and recursively enumerable languages.(5 marks) 7 (b) Intractable Problems(5 marks) 7 (c) Simplification of CFGs(5 marks) 7 (d) Decision properties of regular languages.(5 marks) 7 (e) Rice Theorem(5 marks)