Sathyabama University 2008 B.E Computer Science and Engineering Mathematical Foundation for Computer Science - Question Paper
SATHYABAMA UNIVERSITY
(Established under section 3 of UGC Act, 1956)
Course & Branch: B.E - CSE (Part Time)
Title of the paper: Mathematical Foundation for Computer Science
Semester: IV Max. Marks: 80
Sub.Code: 611PT401 Time: 3 Hours
Date: 22-04-2008 Session: FN
PART A (10 x 2 = 20)
Answer All the Questions
1. A computer company must line 25 programmers to haadle system programming tasks and 40 programmers for applications programming of these hired, 10 will be expected to performs tasks for each type. How many programmers must be lined.
2. Define partial order relation and equivalence relation with an example.
3. Draw the transition diagram of the Non-deterministic finite Automation M = (Q, , d, q0, F) where = {a, b}, Q = {q0, q1, q2}; q0 is its initial state {q1, q2} EF.
|
d |
a |
b |
|
s0 |
{s0, s1} |
{s2} |
|
s1 |
f |
{ s1} |
|
s2 |
{s0, s1} |
f |
4. Define Pushdown Automation.
5. State pumping kmma.
6. Write a regular expression to denote a language L over *, Where = {a, b} such that the 3rd character from right and of the string is always a.
7. Construct a turing machine M for = (a, b} which will convert lower case letters to upper case.
8. Write down the three assumptions to prove that certain language is not recursively enumerable.
9. Define halting problem.
10. State Rice theorem.
PART B (5 x 12 = 60)
Answer All the Questions
11. (a) If f: R R, given by f(x) = x3 2, find f-1.
(b) Define the following functions on the integers f(k) = k + 1; g(k) = 2k and h(k) = 3k
(i) Which of these functions are 1 1
(ii) Find fog and goh.
(or)
12. Use
induction to prove that, 
13. Design Finite Automation which accepts even number of os and even number of 1s. With transistor diagram and transition table.
(or)
14. Construct a deterministic finite state automation (FA) equivalent to NFA with the transition diagram given below.
15. Construct NFA for the regular expression (0 + 1)* with moves.
(or)
16. Consider the grammar G = (V, , R, S) where V = (S, A}, = {a, b}, S Start symbol Rules 
Show that G is an ambiguous grammar.
17. Design a Push down Automation accepting a
language 
(or)
18. Construct a Turing Machine for the language of even number of 1s and even no of 0s one = {0, 1}.
19. (a) Give two properties of recursively enumerable sets which are undecidable.
(b) When a language is said to be recursive (or) recursively enumerable.
(or)
20. State and prove Rices Theorem.
| Earning: Approval pending. |
