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 |
→q0 | {q0,q1} | q1 | {} |
q1 | {q2} | {q1,q2} | {} |
q2 | {q0} | {q2} | {q1} |
State →q1 |
0 q1 |
1 q2 |
q2 | q3 | q2 |
q3 | q1 | q2 |
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)