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.

Sem 3 Subjects (6)View Full Semester Overview →

ENSH 201Engineering Mathematics III ENSH 204Communication English ENCT 201Computer Graphics and Visualization ENCT 202Foundation of Data Science ENCT 203Theory of Computation ENEX 201Microprocessors

Jump to:PDF Papers Most Asked PYQs Past 10 Years Syllabus Marks Scheme

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 40 of 40 top repeated questions

5 Chapters · Click any chapter to expand

Year-wise & Session-wise Exam Papers

Complete questions from each exam session (Regular & Back exams from 2082 to 2069) for Theory of Computation. Click any session paper to expand.

Showing 405 questions across 27 exam session papers

Institute of Engineering • 2083 Baishakh Board Examination

Q1[3 Marks]Finite Automata and Regular Language

Determine regular expression for the following language

L = {w \in {a, b}^{*} : w contains at-least one ’a’ \n **[OR]** \n at-least one ’bb’}

Q2[6 Marks]Finite Automata and Regular Language

Design DFA for following language

L = {w : w \in {a, b}^{*}, w has odd number of ’a’ and odd number of ’b’}

. Also Test your design for "aabbba".

Q3[7 Marks]Context Free Grammar and Pushdown Automata

Design a PDA which accepts all the strings of language

L = {a^{n} b^{m} c^{m} d^{n} : n, m > 0}

Q4[1 Marks]Introduction to Formal Language, Logic and Proof

Define diagonalization principle. Explain principle of mathematical induction with suitable example.

Q5[2 Marks]Context Free Grammar and Pushdown Automata

Explain ambiguity in CFG with example. Write the CFG for the language

L = {a^{i} b^{j} c^{k} : i = j or j = k}

. Generate the strings

a^{3} b^{4} c^{4}

using your grammar.

Q6[2 Marks]Finite Automata and Regular Language

State the pumping lemma for the regular languages. Show that the Language

L = {0^{n^{2}} ∣ n \geq 1}

not regular e.g. if

n = 1, w = 0, n = 2, w = 0000. n = 3, w = 00000000

Q7[6 Marks]Context Free Grammar and Pushdown Automata

Convert the following CFG into CNF.

G = (V, Σ, R, S)

where

V = {S, X, Y}, Σ = {a, b, c}

and

R

given as:

S \to a X b X

$X \to aY | bY | \epsilon$

Y \to X ∣ c

Q8[2 Marks]Turing Machine

Define Turing Machine. Design a single tape deterministic Turing Machine which reverses the given string

w

, over alphabet

Σ = {a, b}

Q9[2 Marks]Turing Machine

Differentiate between context free and unrestricted grammars. Design a turing machine that replaces symbol 'a' with 'b' and 'b' with 'a' for any string

w \in {a, b}^{*}

. Show the processing of machine (configuration transition) for string "ababa".

Q10[5 Marks]Decidability and Computational Complexity

What is "Halting Problem"? How can you prove that it is unsolvable?

Q11[2 Marks]Introduction to Formal Language, Logic and Proof

Define the term Turing decidable. Show that union and intersection of two recursive languages is recursive.

Q12[1 Marks]Decidability and Computational Complexity

Define polynomial time reduction. Explain P and NP problems by means of reference to polynomial time reduction with examples.

Curriculum Syllabus & Course Topics

Sourced from TU curriculum portal

Full Syllabus (PDF)

Chapter-wise Units & Micro-Syllabus Topics (6 Units)

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. 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. 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. 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. 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. 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.

Authentic IOE Past Papers

Free Direct PDF Download

Curriculum Syllabus & Marking Scheme

Past Question Papers (PDF)

3rd-sem_Theory of Computation.pdf

Most Frequently Asked Questions

Introduction to Formal Language, Logic and Proof

Finite Automata and Regular Language

Context Free Grammar and Pushdown Automata

Turing Machine

Decidability and Computational Complexity

Year-wise & Session-wise Exam Papers

Curriculum Syllabus & Course Topics

1. Introduction to Formal Language, Logic and Proof

2. Finite Automata and Regular Language

3. Context Free Grammar and Pushdown Automata

4. Turing Machine

5. Decidability and Computational Complexity

6. Automata Theory and Compiler

Examination Scheme & Marks Distribution

Evaluation Structure

Exam Preparation Guidelines