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: Reena Malik Member Level: Diamond Posted Date: 22 May 2008
|
2005 Indira Gandhi National Open University (IGNOU) B.C.A CS73 : THEORY OF COMPUTER SCIENCE Question paper
BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination
December, 2005
CS73 : 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 finite automata. Explain the parts of automata. (6)
(b) Define CFG, also giving an example. (6)
(c) State the satisfiability problem (SAT). Also explain SAT using an example. (6)
(d) (i) Give the regular expression for a language over the alphabet {a, b}, of strings of odd length.
(ii) Give the regular expression for a language over the alphabet {0, 1}, of strings which have '1' as the third symbol from left.
(iii) Display the typical state transition for a Moore machine, expiaining the labels used. (6)
(e) Consider the following productions:
S ? aB/bA
A ? aS/bAA/a
B ? bS/aBB/b
For the string aabbbaabba, find
(i) the left most derivation
(ii) Parse tree. (6)
2. (a) State and prove the Pumping lemma for regular expressions. (8)
(b) For two recursive languages L1 and L2 determine whether or not L1 n L2 is Turing Decidable. (4)
(c) Describe recursive production through an example. (3)
3. (a) Differentiate "Partial" function from "Total" function. Also give one example for each of them. (4)
(b) Define an NP-complete problem with an example. (3)
(c) Give the state transition graph and state transition table for the elevator controller that serves two floors. (8)
4. (a) Determine the Closure property of CFLs under the following set operations : (9)
(i) Union
(ii) Kleene star
(iii) Complementation
(b) Prove that, if f(x) = 8x3+5x2+7, then (6)
(i) f(x) = ?(x), and
(ii) f(x) = ?(x2)
5. (a) Explain the halt state version of a TM. (7)
(b) Build a PDA that accepts the language odd palindrome over the alphabet {0, 1}. Give the computation sequence for the input 0110110. (8)
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
|