Course Content

Other Courses

Tribhuvan university > CSIT - 2065 Syllabus > Theory of Computation

Theory of Computation - Syllabus

Syllabus Notes Old Questions Unit Wise Questions Question Bank

Embark on a profound academic exploration as you delve into the Theory of Computation course () within the distinguished Tribhuvan university's CSIT department. Aligned with the 2065 Syllabus, this course (CSC-251) seamlessly merges theoretical frameworks with practical sessions, ensuring a comprehensive understanding of the subject. Rigorous assessment based on a 80+20 marks system, coupled with a challenging passing threshold of , propels students to strive for excellence, fostering a deeper grasp of the course content.

This 3 credit-hour journey unfolds as a holistic learning experience, bridging theory and application. Beyond theoretical comprehension, students actively engage in practical sessions, acquiring valuable skills for real-world scenarios. Immerse yourself in this well-structured course, where each element, from the course description to interactive sessions, is meticulously crafted to shape a well-rounded and insightful academic experience.


Course Synopsis:    Deterministic and non-deterministic finite state machines, regular expressions, languages and their properties. Context free grammars, push down automata, Turing machines and computability, undecidable and intractable problems, and Computational complexity.

Goal:  To gain understanding of the abstract models of computation and formal language approach to computation.

Units

Unit 1

1.1    Review of Mathematical Preliminaries: Sets, Logic, Functions, Relations, Languages, Proofs.

1.2    Finite Automata: Deterministic and Non-deterministic Finite Automata, Equivalence of Deterministic and Non-deterministic Finite Automata, Finite Automata with Epsilon-Transition.

1.3  Regular Expressions and Languages, Equivalence of Regular Expressions and Finite Automata, Algebraic Laws for Regular Expressions, Properties of Regular Ranguages, Pumping Lemma for Regular Languages, Minimization of Finite State Machine.


Unit 2

2.1    Context-Free Grammar, Parse Trees, Derivation and Ambiguity, Normal Forms(CNF and GNF) of Context-Free Grammar, Regular Grammars, Closure Properties of Context-Free Languages, Proving a Language to be Non-Context-Free.

2.2  Push Down Automata (PDA), Language of PDA, Deterministic and Non-deterministic PDA, Equivalence of PDA's and CFG,s.


Unit 3

3.1   Introduction to Turing Machines, Computation by Turing Machines, Variants of Turing Machines, Non-deterministic Turing Machines, Turing Enumerable Languages.

3.2   Church's Thesis and Algorithm, Universal Turing Machines, Halting Problems, Turing Machines and Computers.


Unit 4

4.1 Undecidability: Recursive and Recursively Enumerable Languages, Encoding of  Turing Machine, Universal  Language, Unrestricted  Grammars and Chomsky  Hierarchy, Unsolvable Problems by Turing Machines, Undecidable Problems,  Post's Correspondence Problem.


   4.2  Computational Complexity and Intractable Problems, Measuring Complexity,  Class P, Class NP, NP-Completeness and Problem Reduction , NP-Complete  Problems.