Question Paper: Theoretical Computer Science : Question Paper Dec 2014 - Computer Engineering (Semester 4) | Mumbai University (MU)
0

## 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 wR|W? (a+b)} is not regular where wR 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 {an-1 b2n+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
{an bm|n, m≥0 and m≥n}.
(10 marks)
6 (b) Design PDA to check even parentheses over Σ={0,1}.(10 marks)