Theoretical Computer Science : Question Paper Dec 2016 - Computer Engineering (Semester 4)

10views

written 6.8 years ago by

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
→q₀	{q₀,q₁}	q₁	{}
q₁	{q₂}	{q₁,q₂}	{}
q₂	{q₀}	{q₂}	{q₁}

(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 0ⁿ1ⁿⁿ(10 marks) 4(a) Draw a state diagram and construct a regular expression corresponding to the following state transition table.

State →q₁	0 q₁	1 q₂
q₂	q₃	q₂
q₃	q₁	q₂

(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 COMMENT EDIT