Test Papers / Previous Question Papers of IGNOU CS73 Theory of Computer Science December 2005

BACHELOR IN COMPUTER APPLICATIONS
Term-End Examination

December, 2005

CS73 : THEORY OF COMPUTER SCIENCE

Time: 3 hours
Maximum Marks: 75

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 L₁ and L₂ determine whether or not L₁ ∩ L₂ 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) = 8x³+5x²+7, then (6)
(i) f(x) = ω(x), and
(ii) f(x) = ω(x²)

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)