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²ⁿ⁺¹ | 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ⁿ b^m|n, m≥0 and m≥n}.(10 marks) 6 (b) Design PDA to check even parentheses over Σ={0,1}.(10 marks)