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

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 m_i.

(f) Explain the notations Θ, Ω and ω. (6)

2. (a) Differentiate between any three types of grammars, based on their production rules. (6)

(b) Prove that L = {aⁿb^maⁿb^m ⌉ 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 {aⁿb^m} ⌉ 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 = {aⁿb^maⁿ ⌉ 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