Course Code : CS-73

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

Maximum Marks: 10

Last Date of Submission : 15^th April, 2006

This is a Tutor Marked Assignment. There are three questions in this assignment. Answer all the questions. You may use illustrations and diagrams to enhance explanations.

Question 1: Define the following concepts formally:

a) Non-Deterministic Finite Automata

b) Context-Free Grammar

c) Godel Number

d) Regular Language

e) Primitive Recursive Function

f) Turing Machine

g) Unsolvable Problem

h) Turing-Decidable Problem

i) Mealy Automata

j) Universal Turing Machine ( 5 Marks)

Question 2: Construct a Deterministic Finite Automata accepting the following set:

{w E (0, 1)*: w has an odd number of 0's and even number of 1's } (3 Marks)

Question 3: Describe informally language accepted by the Deterministic Finite Automata (2 marks)