BSc CSIT (TU) Science Theory of Computation (BSc CSIT, CSC257) Question Paper 2080
This is the official BSc CSIT (TU) (Science stream) Theory of Computation (BSc CSIT, CSC257) question paper for 2080, 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 2080 paper is a great way to practise under real exam conditions.
Section A: Long Answer Questions
Attempt any TWO questions.
What is a Non-deterministic Finite Automaton (NFA)? Construct an NFA that accepts the set of strings over {0, 1} ending with '01' and convert it into an equivalent DFA using the subset construction method.
State and prove the Pumping Lemma for regular languages. Using it, prove that the language L = { a^n b^n | n >= 0 } is not regular.
Define context-free grammar (CFG). Convert the following CFG into an equivalent grammar in Chomsky Normal Form (CNF): S -> ASA | aB, A -> B | S, B -> b | epsilon.
Section B: Short Answer Questions
Attempt any EIGHT questions.
Explain the closure properties of regular languages.
What is the membership problem? Explain the CYK algorithm in brief.
Construct an NFA for the regular expression (0+1)*1.
Explain Rice's theorem in brief.
Define alphabet, string, and language with examples.
Differentiate between DFA and NFA.
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'.