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

Theoretical Computer Science - May 2016

Computer Engineering (Semester 4)

(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) Explain post correspondence problem.(5 marks) 1(b) Differentiate between NFA and DFA.(5 marks) 1(c) Show that language L = {0i | i is prime number} is not regular(5 marks) 1(d) Compare recursive and recursively enumerable languages.(5 marks) 2(a) Design the DFA to accept all the binary strings over ∑={0, 1} that are beginning with 1 and having its decimal value multiple of 5.(10 marks) 2(b) Design DPDA to accept language L = {x ∈ {1, b}* | N1 (x) > Nb (x)}. Na (x) > Nb (x) means number of a's are greater than number of b's in string x.(10 marks) 3(a) Explain variations and equivalence of Turing machine.(10 marks) 3(b) State and prove pumping lemma for context free languages.(10 marks) 4(a) Design mealy machine to find out 2's complement of a binary number.(10 marks) 4(b) Convert the following NFA to an equivalent DFA

State a b
→ q0 {q0, q1} {q1} {}
q1 {q2} {q1, q2} {}
*q2 {q0} {q2} {q1}
(10 marks) 5(a) Consider the following grammar G = (V, T, P, S), V = {S, X}, T = {a, b} and productions P are
S → aSb | aX
X → Xa | Sa | a
Convert this grammar in Greibach Normal Form (GNF).
(10 marks)
5(b) State and prove Rice's theorem.(10 marks) 6(a) Design a Tuning machine as an acceptor foe the language
{anbm | n , m ≥ 0 and m ≥ n}
(10 marks)
6(b) Design PDA to check even parentheses over ∑={0, 1}.(10 marks)


Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more