## Theoretical Computer Science - Dec 2016

### 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)** Design a DFA over an alphabet ∑={a, b} to recognize a language in which every 'a' is followed by 'b'.(5 marks)
**1(b)** Give formal definition of a Push Down Automata.(5 marks)
**1(c)** State and explain the power and limitations of a Turing machine.(5 marks)
**1(d)** Design a mealy machine to determine the residue mod 3 of a binary number.(5 marks)
**2(a)** Convert the following NFA to an equivalent DFA

State | a | b | c |

→q_{0} |
{q_{0},q_{1}} |
q_{1} |
{} |

q_{1} |
{q_{2}} |
{q_{1},q_{2}} |
{} |

q_{2} |
{q_{0}} |
{q_{2}} |
{q_{1}} |

**2(b)**State and explain pumping lemma for regular languages. Using pumping lemma prove that the language $ L=\left \{ o^n1^n|n\geq 0 \right \} $/ is not regular.(10 marks)

**3(a)**Design a Turing machine that computers a function f(m,n)=m+n i.e. addition of two integers.(10 marks)

**3(b)**Design a Turing machine to accept the language 0

^{n}1

^{n}

^{n}(10 marks)

**4(a)**Draw a state diagram and construct a regular expression corresponding to the following state transition table.

State →q _{1} |
0 q _{1} |
1 q _{2} |

q_{2} |
q_{3} |
q_{2} |

q_{3} |
q_{1} |
q_{2} |

**4(b)**State and explain decision properties of regular languages(10 marks)

**5(a)**i) Convert the following CFG to GNF

S→AA|a

A→SS|b(10 marks)

**5(b)**Design a PDA correponding to the to the grammar S→aSA |ε

A→bB

B→b(10 marks)

### Write a short note any two Q6.(a,b,c,d)

**6(a)** Recursive and Recursively Enumerable Languages.(10 marks)
**6(b)** Chomsky Hierarchy(10 marks)
**6(c)** Rice's Theorem(10 marks)
**6(d)** Halting problem(10 marks)