My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
Download Model question papers & previous years question papers
|
Posted By: S.Yamini Member Level: Diamond Posted Date: 08 May 2008
|
2005 Indira Gandhi National Open University (IGNOU) B.C.A Theory of Computer Science Question paper
Test Papers / Previous Question Papers of IGNOU CS73 Theory of Computer Science December 2005
BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
December, 2005
CS73 (S) : THEORY OF COMPUTER SCIENCE
Time: 3 hours
Maximum Marks: 75
Note : Question number 1 is compulsory. Answer any three questions from the rest.
1. (a) Define Grammar State the Chomsky's classification of grammars. (6)
(b) Find the equivalent finite automata for the regular expression (a + b)* (ab + ba) (a + b)*. (6)
(c) Give one application each for the following : (6)
CFG, Regular expression, Finite automata.
(d) Define the following terms in the context of Turing machine.
Instantaneous description, Halted configuration. (3)
(e) Give the guiding rules for constructing a Turing machine m out of mi.
(f) Explain the notations T, O and ?. (6)
2. (a) Differentiate between any three types of grammars, based on their production rules. (6)
(b) Prove that L = {anbmanbm ? n, m = 1} is not context free.
(c) State any three undecidable problems. (3)
3. (a) Construct the two way Turing machine to accept the language {anbm} ? n = 1, m= 0}. (5)
(b) Show that the VERTEX-COVER Problem is NP-Complete. (7)
(c) Consider the following Moore machine :
-----DIAGRAM-----
Give the output for the following inputs :
00110010, 110101100. (3)
4. (a) What are the considerations for extension of Turing machines? Explain any two considerations in detail. (9)
(b) Give the transition diagram for a traffic signal. (6)
5. (a) Construct a PDA that can accept the language L over {a, b}, where L = {anbman ? n, m = 0}. Also show the execution of your PDA for the inputs aaabbaaa, aabbba. (9)
(b) Explain the equivalence of regular expression and FA. Also, give the transition diagram for the following : (6)
(i) R = P + Q
(ii) R = P*
(iii) R = PQ
Return to question paper search
|
|
|
Submit Previous Years University Question Papers and make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.
|
Watch TV Channels
|