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

## 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 →q0 {q0,q1} q1 {} q1 {q2} {q1,q2} {} q2 {q0} {q2} {q1}
(10 marks) 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 0n1nn(10 marks) 4(a) Draw a state diagram and construct a regular expression corresponding to the following state transition table.
 State →q1 0 q1 1 q2 q2 q3 q2 q3 q1 q2
(10 marks)
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)