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)