## 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)