## Theoretical Computer Science - May 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)** Explain post correspondence problem.(5 marks)
**1(b)** Differentiate between NFA and DFA.(5 marks)
**1(c)** Show that language L = {0^{i} | i is prime number} is not regular(5 marks)
**1(d)** Compare recursive and recursively enumerable languages.(5 marks)
**2(a)** Design the DFA to accept all the binary strings over ∑={0, 1} that are beginning with 1 and having its decimal value multiple of 5.(10 marks)
**2(b)** Design DPDA to accept language L = {x ∈ {1, b}* | N_{1} (x) > N_{b} (x)}. N_{a} (x) > N_{b} (x) means number of a's are greater than number of b's in string x.(10 marks)
**3(a)** Explain variations and equivalence of Turing machine.(10 marks)
**3(b)** State and prove pumping lemma for context free languages.(10 marks)
**4(a)** Design mealy machine to find out 2's complement of a binary number.(10 marks)
**4(b)** Convert the following NFA to an equivalent DFA

State | a | b | ∈ |

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

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

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

**5(a)**Consider the following grammar G = (V, T, P, S), V = {S, X}, T = {a, b} and productions P are

S → aSb | aX

X → Xa | Sa | a

Convert this grammar in Greibach Normal Form (GNF).(10 marks)

**5(b)**State and prove Rice's theorem.(10 marks)

**6(a)**Design a Tuning machine as an acceptor foe the language

{a

^{n}b

^{m}| n , m ≥ 0 and m ≥ n}(10 marks)

**6(b)**Design PDA to check even parentheses over ∑={0, 1}.(10 marks)