CS-73 :           Theory of Computer Science

Assignment Code                  :           BCA(6)-73/Assignment/2009

Maximum Marks                  :           25

Last date of Submission        :           30^th April, 2009/30^th October, 2009

 

This assignment is having five questions. Answer all the questions. 

 

Q. 1  Define the following concepts formally/mathematically, with one example for each:

 

a)        Regular Language

b)       Primitive Recursive Function

c)        Turing Machine

d)       Unsolvable Problem

e)        Turing-Decidable Problem

f)        Mealy Automata

g)       Universal Turing Machine

h)       Deterministic Finite Automata

i)         Context-Free Grammar

j)         Godel Number                                            (5 marks)

Q. 2  Construct a DFA (Deterministic Finite Automata) accepting the following Set:

{w ? { a , b }*:w has an even number of a’s and odd number of b’s }                                       (5 marks)

Q. 3 Construct Turing Machine for the following languages:

 

 

Download Attached PDF

• Political Science (4)
  (82 downloads)