## Theoretical Computer Science - May 2014

### 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)** Explain CNF and GNF with example.(5 marks)
**1(c)** state and prove closure properties of context free languages.(5 marks)
**1(d)** Give Applications of Regular Expression and finite Automata(5 marks)
**2(a)** Construct an NFA with epsilon transition for following RE.

(00+11)*(10)*(5 marks)
**2(b)** Give formal definition of regular expression.Give R>E for following:

Set of all strings over {1,0}that end with and has no substring 00.

Set of all strings over {1,0}with even number of 1's followed by odd number of 0's(5 marks)
**2(c)** Compare and Construct Moore and Melay Machine.Construct Moore Machine to find out the residue-modulo-3 for binary numbers.(10 marks)
**3(a)** Consider the following grammar:

S$\rightarrow$I C t S |I C t S e S|a

C$\rightarrow$b

For the string 'ibtibtaen find the following:

i)Leftmost derivation

ii)Rightmost derivation

iii)Parse tree

iv)Check if the above grammar is Ambiguous.
(10 marks)
**3(b)** Design PDA that checks for well-formed parentheses.(10 marks)
**4(a)** Design a TM that recognizes palindrome strings where $\sum$={0,1}
(10 marks)
**4(b)** Construct NFA that accept a set of all strings over {a,b}ending with "abb"Covert this NFA to Equivalent DFA.(10 marks)
**5(a)** Convert the following Grammar to CNF form:

S$\rightarrow$ ABA

A$\rightarrow$aA|bA| $\epsilon$

B$\rightarrow$ bB|aA|$\epsilon$(10 marks)
**5(b)** Give and explain the formal statement of pumping lemma for languages and use it to prove that the following languages is not regular:

L={a^{n}b^{n}|n>=1}(10 marks)

### Write short notes on:

**6(a)** Chomsky Hierarchy of Grammar(5 marks)
**6(b)** Variants of Turning machine(5 marks)
**6(c)** Rice's Theorem(5 marks)
**6(d)** Recursive and Recursively enumerable languages.(5 marks)