Tamil Nadu Open University (TNOU) 2009-3rd Year B.C.A Computer Application .>>THEORY OF COMPUTER SCIENCE>>E .>> - Question Paper

B.C.A. DEGREE EXAMINATION
JUNE 2009.

Third Year

THEORY OF COMPUTER SCIENCE

Time : 3 hours Maximum marks : 75

PART A (5 5 = 25 marks)

Answer any FIVE questions.

1.         Define Universal set, empty set, singleton set.

2.         Give example of transitive and reflexive relation.

3.         Explain tautology and contradiction with example.

4.         Show that .

5.         Define connected and disconnected graphs.

6.         Define context free grammar with example and give a grammar to generate palindrome type of string.

7.         Define ambiguity and write points to remove ambiguity.

PART B (5 10 = 50 marks)

Answer any FIVE questions.

8.         Let r be a relation on A. Then prove the following :

             (a) If r is reflexive then .

             (b) If r is symmetric, then is symmetric.

9.         Show that .

10.       Write the truth table for .

11.       Explain Turing machine in detail.

12.       Design a finite state automata that accepts precisely those strings over that contain an odd number of s.

13.       Prove that the maximum number of edges in a simple graph with vertices is .

14.       Explain with an example the pre order, post order and inorder traversal of binary tree.