## Theoretical Computer Science - Dec 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)** Give chomsky hierachy of grammar with examples.(5 marks)
**1 (b)** State and explain any 5 closure properties of regular language.(5 marks)
**1 (c)** Compare recursive and recursively enumerable language.(5 marks)
**1 (d)** State and prove equivalence of NFA and DFA.(5 marks)
**2 (a)** Design a DFA to accept strings over the alphabet set {a, b} that begin with 'aa' but not end with 'aa'.(10 marks)
**2 (b)** Covert (0+$\epsilon$) (1 0)*($\epsilon$+1) into NFA with $\epsilon$-moves and hence obtain a DFA.
**(10 marks)
** 3 (a) Design a MOORE and MEALY machine to decrement a binary number.(10 marks)
3 (b) Give statement of pumping lemma for regular sets and hence prove that {w c w^{R}|W? (a+b)*} is not regular where w

^{R}is reverse of w.(10 marks)

**4 (a)**Obtain leftmost derivation, rightmost derivation and derivation tree for the string "cccbaccba". The grammar us S→Ssa|SSb|c(10 marks)

**4 (b)**Design Turing machine as generator to add two binary numbers and hence simulate for "110+10". Hint: Assume two way infinite tape.(10 marks)

**5 (a)**Design a PDA to accept language {a

^{n-1}b

^{2n+1}| n≥1}.(10 marks)

**5 (b)**Convert the below given grammar to Chomsky Normal Form (CNF) and Griebach Normal Form (GNF) E→E+E|E*E|(E)|id

Consider "id" as a single terminal/symbol.(10 marks)

**6 (a)**Design a Turing machine as acceptor for 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)