CS-73 : Theory Of Computer Science-December,2006

  JHARKHAND BOARD You are here
BACHELOR IN COMPUTER APPLICATIONS

Term-End Examination

December, 2006

CS-73 : THEORY OF COMPUTER SCIENCE

Time : 3 hours Maximum Marks : 75

Note : Question number 1 is compulsory. Attempt any three questions from the rest.

1. (a) What is Kleene closure ? Write Kleene closure of the following: (2+1+1=4)

(i) {bb, c)

(ii) {0, 1)

(b) What are primitive recursive functions ? Describe the initial functions and structuring rules used to obtain primitive recursive function. (2+4=6)

(c) Describe the concept of Universal Turing Machine. (5)

(d) Write a short note on Post Correspondence Problem. (5)

(e) Diagrammatically show the processing of 00101 through the state transition machine shown below. (5)

(f) Differentiate between Moore Machine and Mealey Machine. (Diagram is must)(5)

2. (a) Construct the finite automata corresponding to the following regular expression :

(0 + 1)* (00 + 11) (0 + 1)*

(b) Define Godel number. (2)

(c) Prove the following properties of regular expressions : (2+3=5)

(i) R+R=R

(ii) R(S + T) = RS + RT

3. (a) Convert the following Moore Machine to equivalent Mealey Machine.(7)

(b) What is finite automata ? What are the applications of finite automata ? (5)

(c) Differentiate between CFG and CSG. (3)

4. (a) What is a NP complete problem ? Explain how NP completeness of the problem can be established. (6)

(b) Define Pumping Lemma. (4)

(c) Let F(x) = 2x3 + 3x2 + 1, then prove(5)

(i) F(x) = O(xn) for n >= 4

(ii) F(x) = O(x3)

5. (a) Write a short note on halting problem of Turing Machine. (5)

(b) Describe Chomsky's classification of grammars. (5)

(c) Describe the relationship between CNF and CFG. (5)



  « Marking Scheme Class – X (2008-2009…) CS-73 : Theory Of Computer Science-june,2006 »  

  Posted on Thursday, December 4th, 2008 at 11:16 AM under   JHARKHAND BOARD | RSS 2.0 Feed