Theory of Computation-TOC IOE Notes, Tutorial and Solution

Theory of Computation (TOC) is included in the course of Bachelor in Computer Engineering (BCT) by Institute of Enigneering (IOE), Tribhuvan University (TU). The course is designed to provide basic understanding of theory of automata, formal languages, turing machines and computational complexity.

The complete course content/syllabus with marking scheme of the subject can be accessed from Theory of Computation -TOC IOE Syllabus page.

The following notes are compiled by Hari Prasad Pokhrel who has been teaching in various Engineering Colleges in Nepal since long time. We would like to thank him for his hard effort in compiling the notes of all subjects and helping for making educational resources accessible easily.

The notes of TOC are in PDF format and are separately built on the basis of chapters or course contents provided by the Computer Engineering Department of IOE. Click on the corresponding link to read online or download the notes.

1. Introduction: It includes introduction to set, relation, function, Proof techniques and alphabets, language, regular expression. Read: PDF note of Chapter 1 – Introduction to Theory of Computation.
2. Finite Automata: The second chapter aims to provide general information on Finite Automata (Deterministic and Non‐Deterministic), equivalence of regular language and finite automata, regular language and its properties, Pumping lemma for regular language & decision algorithms for regular languages. Download: PDF note of Chapter 2 – Finite Automata.
3. Context free language: The third chaper mainly concerns with context free language & grammar and their simplification, derivative trees, Chomsky normal form (CNF), Push Down Automata (PDA) and its equivalence with context free language (CFL). Apart from these, it includes Pumping lemma for context free language and Decision algorithms for context free language. Download: Note of Chapter 3 – Context Free Language.
4. Turing machine: Fourth Chapter deals with turing machine ( its definition, notation & Computation), Extensions of Turing machine and Unrestricted grammar including Recursive function theory. Read: Chapter 4 Note – Turing Machine.
5. Undecidability: Chapter 5 includes the micro syllabus of computational complexity, Class P & NP complete problems. Click HERE to access note of the fifth chapter of TOC note.
6. Computational Complexity

Tutorials and Solutions:

The following two links consist of tutorial questions along with solutions to some problems.

Tutorial 1

Tutorial 2

Update on 8th April:

Old question collection for TOC is in Theory of Computation Old Question Collection post.