Course Code : CS-73

Assignment Number : BCA(VI)-73/Project/06

Maximum Marks: 15

Last Date of Submission : 30^th April, 2006

There are three questions in this project assignment. Answer all the questions.

Question 1: Construct one grammar for each of the following languages: (5 marks)

(a) { oⁿ 1^m : m < n}

(b) { w E (0, 1)* : w = w^R}

Question 2: Construct one Turing Machine for computing each of the following functions : (5 marks)

(i) f (m, n) = m * n, where '*' denotes multiplication

(ii) f (m, n) = {m - n if m > n,
f (m, n) = { 0 if m < n

Question 3: Show that each of the following functions is primitive recursive: (5 marks)

(i) f (m, n) = 4m+5n

(ii) f (m, n) = (2m)⁵ⁿ