## 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^{n}b^{n} 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)