BSc CSIT (TU) Science Theory of Computation (BSc CSIT, CSC257) Question Paper 2081
This is the official BSc CSIT (TU) (Science stream) Theory of Computation (BSc CSIT, CSC257) question paper for 2081, 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 2081 paper is a great way to practise under real exam conditions.
Section A: Long Answer Questions
Attempt any TWO questions.
What is a Pushdown Automaton (PDA)? Design a PDA that accepts the language L = { a^n b^n | n >= 1 } and trace its moves for the string 'aabb'.
Define a Turing Machine formally. Design a Turing Machine that accepts the language L = { a^n b^n c^n | n >= 1 } and explain its working with a transition diagram.
Explain the relationship between regular expressions and finite automata. Show that for every regular expression there is an epsilon-NFA accepting the same language, and convert (a+b)*ab into an equivalent finite automaton.
Section B: Short Answer Questions
Attempt any EIGHT questions.
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.
What is a Universal Turing Machine? Explain its significance.
Differentiate between recursive and recursively enumerable languages.
Define Mealy and Moore machines and differentiate between them.
Explain the closure properties of regular languages.