IOE PapersTU
PYQs & Syllabus Archive
ENCT 203Bachelor in Computer Engineering · Semester 32 Papers Available

Theory of Computation

Past examination question papers and complete curriculum syllabus for Theory of Computation (ENCT 203), Bachelor in Computer Engineering Semester 3 under Institute of Engineering (IOE), Tribhuvan University.

Past Question Papers (PDF)

Switch tabs to view different exam papers
Available Papers:

3rd-sem_Theory of Computation.pdf

IOE Past Examination Paper

Download PDF
Served via fast CDN. Read in full view or download for offline study.
Drive Mirror ↗Direct Download ↓

Document information: This past examination paper is identified as an IOE/TU academic document and was cataloged from a public Google Drive archive. This independent website did not create the examination paper and is not affiliated with TU or IOE.

Rights holders can request correction or removal by emailing subeshgaming@gmail.com with this page URL and supporting details.

Most Frequently Asked Questions

Top recurring IOE board exam questions for Theory of Computation with verified mark schemes, formula notation, and recurrence frequency.

Showing 30 of 30 top repeated questions

Introduction to Formal Language, Logic and Proof

4 Questions
#1Repeated 5 Times[4 Marks]Introduction to Formal Language, Logic and Proof
Define equivalence relation and partial order relation. Using mathematical induction, show that: (a) for every integer $n \ge 0$, $4^{2n+1} + 3^{n+2}$ is a multiple of 13, and (b) $1^3 + 2^3 + \dots + n^3 = \left[\frac{n(n+1)}{2}\right]^2$.
Appeared in:2082 Chaitra2082 Kartik2081 Chaitra2079 Chaitra2076 Chaitra
#2Repeated 4 Times[3 Marks]Introduction to Formal Language, Logic and Proof
Using rules of inference and the principle of resolution in propositional logic, prove that the premises 'If it is raining then Prem has his umbrella', 'Prem does not have his umbrella or he does not get wet', and 'It is raining or Prem does not get wet' logically imply 'Prem does not get wet'.
Appeared in:2082 Chaitra2081 Chaitra2077 Magh2074 Chaitra
#3Repeated 4 Times[5 Marks]Introduction to Formal Language, Logic and Proof
Explain how tokens are generated by the lexical analyzer phase of a compiler using Finite Automata. Describe how a syntax analyzer uses Context-Free Grammars to construct parse trees for expressions like $r = a + b * c / (d * e)$.
Appeared in:2082 Chaitra2082 Kartik2081 Chaitra2078 Chaitra
#4Repeated 3 Times[8 Marks]Introduction to Formal Language, Logic and Proof
Explain the Chomsky Hierarchy of Formal Languages: Type-0 (Unrestricted), Type-1 (Context-Sensitive), Type-2 (Context-Free), and Type-3 (Regular). List their defining grammar formats, accepting automata, and closure properties under union, intersection, and complementation.
Appeared in:2082 Chaitra2081 Chaitra2078 Chaitra

Finite Automata and Regular Language

7 Questions
#1Repeated 6 Times[4 Marks]Finite Automata and Regular Language
Design a DFA over $\Sigma = \{0, 1\}$ that accepts all strings containing an even number of 0's and odd number of 1's (or number of 1's multiple of 3 and number of 0's multiple of 2). Verify your design by tracing the transition sequence for $w = 1010111001$.
Appeared in:2082 Chaitra2082 Kartik2081 Chaitra2078 Chaitra2076 Baisakh2073 Chaitra
#2Repeated 6 Times[6 Marks]Finite Automata and Regular Language
Explain how to minimize the states of a DFA using the table filling algorithm (equivalence theorem). Convert a given NFA with $\epsilon$-transitions to an equivalent DFA and minimize the resulting DFA.
Appeared in:2082 Chaitra2082 Kartik2081 Chaitra2079 Chaitra2076 Chaitra2074 Chaitra
#3Repeated 5 Times[4 Marks]Finite Automata and Regular Language
State the Pumping Lemma for regular languages. Use the pumping lemma to prove that the language $L = \{a^p \mid p \text{ is a prime number}\}$ or $L = \{0^n 1^n \mid n \ge 0\}$ is not regular.
Appeared in:2082 Chaitra2081 Chaitra2078 Chaitra2076 Baisakh2074 Chaitra
#4Repeated 5 Times[4 Marks]Finite Automata and Regular Language
Write regular expressions for: (a) strings containing odd number of 1's followed by even number of 0's or vice versa, and (b) strings containing at least one 'a' and two 'b's over alphabet $\Sigma = \{a, b\}$. Obtain a regular expression from a given state transition diagram using Arden's Theorem.
Appeared in:2082 Chaitra2082 Kartik2081 Chaitra2079 Chaitra2076 Baisakh
#5Repeated 3 Times[8 Marks]Finite Automata and Regular Language
State and prove the Pumping Lemma for Regular Languages. Use it to prove that the languages $L = \{0^n 1^n \mid n \ge 0\}$ and $L = \{a^p \mid p \text{ is a prime number}\}$ are not regular.
Appeared in:2082 Chaitra2081 Chaitra2078 Chaitra
#6Repeated 3 Times[8 Marks]Finite Automata and Regular Language
Convert a given Non-Deterministic Finite Automaton with epsilon-transitions (\epsilon-NFA) to an equivalent Deterministic Finite Automaton (DFA) using the subset construction algorithm with $\epsilon$-closure calculations.
Appeared in:2082 Chaitra2081 Chaitra2079 Chaitra
#7Repeated 3 Times[8 Marks]Finite Automata and Regular Language
Minimize a given DFA using the Table-Filling Algorithm (Myhill-Nerode theorem equivalence partitioning). Show the step-by-step marking of distinguishability pairs and construct the minimal state DFA.
Appeared in:2082 Kartik2080 Chaitra2078 Bhadra

Context Free Grammar and Pushdown Automata

7 Questions
#1Repeated 6 Times[5 Marks]Context Free Grammar and Pushdown Automata
Define Instantaneous Description (ID) of a Pushdown Automaton (PDA). Design a PDA to accept the language $L = \{a^m b^n \mid m, n > 0 \text{ and } m \ge n\}$ (or $L = \{w c w^R \mid w \in \{a, b\}^*\}$). Show how your design recognizes the input string $w = aaaaabbb$.
Appeared in:2082 Chaitra2082 Kartik2081 Chaitra2079 Chaitra2077 Magh2075 Chaitra
#2Repeated 5 Times[5 Marks]Context Free Grammar and Pushdown Automata
Convert the given Context-Free Grammar (CFG) into Chomsky Normal Form (CNF) or Greibach Normal Form (GNF). Step-by-step eliminate $\epsilon$-productions, unit productions, and useless symbols.
Appeared in:2082 Kartik2081 Chaitra2079 Chaitra2077 Magh2075 Chaitra
#3Repeated 4 Times[4 Marks]Context Free Grammar and Pushdown Automata
Prove that Context-Free Languages (CFLs) are closed under Union, Concatenation, and Kleene Star, but are NOT closed under Intersection and Complementation. Give suitable proofs and counterexamples.
Appeared in:2082 Chaitra2082 Kartik2078 Chaitra2075 Chaitra
#4Repeated 3 Times[8 Marks]Context Free Grammar and Pushdown Automata
State and prove the Pumping Lemma for Context-Free Languages (CFL). Use it to prove that the language $L = \{a^n b^n c^n \mid n \ge 1\}$ is not context-free.
Appeared in:2082 Kartik2080 Chaitra2077 Magh
#5Repeated 3 Times[8 Marks]Context Free Grammar and Pushdown Automata
Convert a given Context-Free Grammar (CFG) into Chomsky Normal Form (CNF) step-by-step: elimination of $\epsilon$-productions, elimination of unit productions ($A \to B$), elimination of useless symbols, and restructuring into $A \to BC$ and $A \to a$.
Appeared in:2082 Chaitra2081 Chaitra2077 Magh
#6Repeated 3 Times[8 Marks]Context Free Grammar and Pushdown Automata
Convert a given Context-Free Grammar (CFG) into Greibach Normal Form (GNF) where all production rules are of the form $A \to a \alpha$ with $a \in \Sigma$ and $\alpha \in V^*$. Explain the elimination of left recursion using auxiliary variables.
Appeared in:2082 Kartik2080 Chaitra2076 Chaitra
#7Repeated 3 Times[8 Marks]Context Free Grammar and Pushdown Automata
Explain the equivalence between Acceptance by Final State ($L(M)$) and Acceptance by Empty Stack ($N(M)$) in Pushdown Automata. Provide constructive algorithms to convert a PDA from one acceptance criterion to the other.
Appeared in:2082 Chaitra2081 Chaitra2078 Chaitra

Turing Machine

5 Questions
#1Repeated 6 Times[6 Marks]Turing Machine
Design a Turing Machine that recognizes the language $L = \{a^n b^n c^n \mid n \ge 1\}$ (or $L = \{a^n b^n c^n d^n \mid n \ge 0\}$). Show the transition table, state diagram, and trace how the input string $w = aaabbbccc$ is processed and accepted by your machine.
Appeared in:2082 Chaitra2082 Kartik2081 Chaitra2078 Chaitra2076 Chaitra2074 Chaitra
#2Repeated 5 Times[6 Marks]Turing Machine
Design a Turing Machine that computes the arithmetic function $f(x) = 2x$ (or predecessor/successor function). Explain the architecture and computational power of multi-tape Turing Machines and Turing Machines with storage in states.
Appeared in:2082 Chaitra2082 Kartik2081 Chaitra2077 Magh2074 Chaitra
#3Repeated 4 Times[4 Marks]Turing Machine
Design a Turing Machine that reads an arbitrary binary string on its tape and outputs its 1's complement (or reverses a given string $w$ over alphabet $\{a, b\}$). Trace the execution step-by-step.
Appeared in:2082 Chaitra2082 Kartik2078 Chaitra2075 Chaitra
#4Repeated 3 Times[8 Marks]Turing Machine
Design a Turing Machine that computes the 2's complement of a given binary string or multiplies a unary number by 2 ($f(1^n) = 1^{2n}$). Provide the formal 7-tuple definition, transition table, and trace tape transitions for sample input.
Appeared in:2082 Kartik2080 Chaitra2077 Magh
#5Repeated 3 Times[6 Marks]Turing Machine
Explain the Church-Turing Thesis and the concept of a Universal Turing Machine (UTM). How does a UTM simulate any arbitrary Turing Machine $M$ on input $w$ using binary encoding of states and tape transitions?
Appeared in:2082 Chaitra2081 Chaitra2079 Chaitra

Decidability and Computational Complexity

7 Questions
#1Repeated 5 Times[4 Marks]Decidability and Computational Complexity
State and explain the Church-Turing Thesis. State the Halting Problem of Turing Machines and prove by contradiction that the halting problem is undecidable. Explain the encoding process of a Universal Turing Machine (UTM).
Appeared in:2082 Chaitra2082 Kartik2081 Chaitra2078 Chaitra2075 Chaitra
#2Repeated 5 Times[4 Marks]Decidability and Computational Complexity
Define space and time complexity for Turing Machines. Explain the complexity classes P, NP, NP-Complete, and NP-Hard. Explain why the Boolean Satisfiability problem (SAT) is NP-Complete by Cook's Theorem.
Appeared in:2082 Kartik2081 Chaitra2078 Chaitra2076 Chaitra2073 Chaitra
#3Repeated 4 Times[4 Marks]Decidability and Computational Complexity
Differentiate between Recursive languages and Recursively Enumerable (RE) languages. Prove that if a language $L$ and its complement $\bar{L}$ are both recursively enumerable, then $L$ is recursive.
Appeared in:2082 Kartik2081 Chaitra2079 Chaitra2076 Chaitra
#4Repeated 3 Times[8 Marks]Decidability and Computational Complexity
Define the Halting Problem of Turing Machines. Prove that the Halting Problem $H_{TM} = \{\langle M, w \rangle \mid M \text{ halts on input } w\}$ is undecidable using proof by contradiction and Cantor's diagonalization method.
Appeared in:2082 Kartik2080 Chaitra2078 Bhadra
#5Repeated 3 Times[8 Marks]Decidability and Computational Complexity
Explain the Post Correspondence Problem (PCP) and Modified Post Correspondence Problem (MPCP). Prove that PCP is undecidable by reduction from the Halting Problem or TM Acceptance problem.
Appeared in:2082 Chaitra2081 Chaitra2077 Magh
#6Repeated 3 Times[6 Marks]Decidability and Computational Complexity
State and explain Rice's Theorem on recursive and recursively enumerable languages. Use Rice's Theorem to show that determining whether $L(M) = \emptyset$ or whether $L(M)$ is regular are undecidable problems.
Appeared in:2082 Kartik2080 Chaitra2076 Chaitra
#7Repeated 3 Times[8 Marks]Decidability and Computational Complexity
Define complexity classes P, NP, NP-Complete, and NP-Hard. Explain polynomial-time reduction ($A \le_p B$) and state the Cook-Levin Theorem proving that the Boolean Satisfiability problem (SAT / 3-SAT) is NP-Complete.
Appeared in:2082 Kartik2080 Chaitra2077 Magh

Curriculum Syllabus & Course Topics

Sourced from TU curriculum portal
Full Syllabus (PDF)
Chapter-wise Units & Micro-Syllabus Topics (6 Units)

  1. 1. Introduction to Formal Language, Logic and Proof

    • 1.1Brief review of set theory, function and relation
    • 1.2Propositional logic, expressing statements in propositional logic, rules of inference and proofs in propositional logic, introduction to predicate logic
    • 1.3Proofs, principle of mathematical induction, diagonalization principle, pigeonhole principle
    • 1.4Alphabet and language
    • 1.5Operations on languages: Union, concatenation, Kleene star

  2. 2. Finite Automata and Regular Language

    • 2.1Introduction to finite automata, finite state machine
    • 2.2Deterministic finite automata (DFA), representation of DFA, language of DFA, design of DFA
    • 2.3Non deterministic finite automata (NFA), equivalence of DFA and NFA
    • 2.4Finite automata with epsilon transition (ε - NFA), equivalence of NFA and ε –NFA, equivalence of DFA and ε – NFA
    • 2.5Regular expressions and regular languages
    • 2.6Equivalence of regular expression and finite automata
    • 2.7Closure properties of regular languages
    • 2.8Pumping lemma for regular languages
    • 2.9Decision algorithm for regular language

  3. 3. Context Free Grammar and Pushdown Automata

    • 3.1Introduction to context free grammar (CFG), component of CFG, context free language (CFL)
    • 3.2Types of derivations, parse tree and its construction, ambiguity
    • 3.3Simplification of CFG, normal forms, Chomsky normal form (CNF), Greibach normal form (GNF), Backus-Naur form (BNF)
    • 3.4Closure properties of context free languages
    • 3.5Pumping Lemma for context free languages
    • 3.6Decision algorithm for context free language
    • 3.7Introduction to push down automata (PDA), representation of PDA, operations of PDA, move of a PDA, instantaneous description for PDA
    • 3.8Language of PDA, equivalence of CFL and PDA, conversion of CFG to PDA
    • 3.9Context sensitive grammar

  4. 4. Turing Machine

    • 4.1Introduction to turing machine (TM), representation of TM, move of a TM, instantaneous description for TM
    • 4.2Computing with turing machine
    • 4.3Variants of turing machine
    • 4.4Unrestricted grammar, Chomsky hierarchy of grammar
    • 4.5Recursive function theory

  5. 5. Decidability and Computational Complexity

    • 5.1Church turing thesis
    • 5.2Universal turing machine, encoding of turing machine
    • 5.3Undecidable problem about turing machines, halting problems and its implications
    • 5.4Computational complexity, time and space complexity of a turing machine
    • 5.5Complexity classes class P, class NP, NP‐complete problems

  6. 6. Automata Theory and Compiler

    • 6.1Basic concept of compiler, role of lexical analyzer, lexical analysis with deterministic finite automata
    • 6.2Parser and context free grammar, top down parsing, bottom up parsing, IR parsing

Examination Scheme & Marks Distribution

Evaluation Structure

  • Final Board Theory Exam: 60 Marks (Pass mark: 24)
  • Internal Assessment: 40 Marks (Pass mark: 16)
  • Practical / Lab Exam: 25 or 50 Marks (Continuous lab evaluation + viva, where applicable)

* This is the general current IOE 60/40 scheme; verify course-specific details in the syllabus above.

Exam Preparation Guidelines

  • Review the 2 available past examination papers to identify recurring patterns, core problem types, and chapter weightage.
  • Cross-reference key answers with official syllabus units, standard textbooks, and lecture notes.
  • Structure answers with labeled diagrams, concise bullet points, and highlight final answers in numerical solutions.

Frequently Asked Questions (Theory of Computation)

Q: How can I download Theory of Computation past question papers?

You can preview or download the Theory of Computation question papers (PDF) directly using the built-in viewer on this page with zero redirects or paywalls.

Q: What is the pass mark for Theory of Computation?

The general current scheme is a 60-mark final theory exam and a 40-mark internal assessment, with pass marks of 24 and 16. Verify the course-specific syllabus above.

Q: Where can I find the complete syllabus for this subject?

The available chapter-wise syllabus and topic breakdown is indexed in the Syllabus section above, with links to the curriculum PDF source.

Authentic IOE Past Papers
Free Direct PDF Download
Curriculum Syllabus & Marking Scheme