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)

ADD COMMENTlink
written 17 months ago by gravatar for Team Ques10 Team Ques10 ♦♦ 400
Please log in to add an answer.