BSc CSIT (TU) Science Theory of Computation (BSc CSIT, CSC257) Question Paper 2079
This is the official BSc CSIT (TU) (Science stream) Theory of Computation (BSc CSIT, CSC257) question paper for 2079, as set in the regular annual examination. It carries 60 full marks and a time allowance of 180 minutes, across 12 questions. On Kekkei you can attempt this Theory of Computation (BSc CSIT, CSC257) past paper online with a timer, get instant AI feedback and step-by-step solutions, and track the topics where you lose marks — completely free. Whether you are revising for your BSc CSIT (TU) Theory of Computation (BSc CSIT, CSC257) exam or solving previous years' question papers, this 2079 paper is a great way to practise under real exam conditions.
Section A: Long Answer Questions
Attempt any TWO questions.
Define the complexity classes P and NP. Explain NP-completeness and the concept of polynomial-time reduction with the example of the Satisfiability (SAT) problem.
Minimize the given DFA using the partitioning (table-filling) method and explain each step of the minimization algorithm with a suitable example.
State and prove the Pumping Lemma for context-free languages. Use it to show that L = { a^i b^j c^k | i = j = k } is not context-free.
Section B: Short Answer Questions
Attempt any EIGHT questions.
Construct a DFA that accepts all binary strings ending with '00'.
Explain epsilon-closure with a suitable example.
Write a regular expression for strings over {0,1} that contain at least one '0' and at least one '1'.
State Arden's theorem and explain its use in obtaining a regular expression from a finite automaton.
What is an ambiguous grammar? Show with an example that a grammar is ambiguous.
Eliminate left recursion from the grammar A -> Aa | b.
Explain the conversion of a CFG into Greibach Normal Form (GNF).
Define instantaneous description (ID) of a PDA and explain acceptance by final state and by empty stack.
Explain the working of a multi-tape Turing Machine.