Course Content

Other Courses

Tribhuvan university CSIT 2065 Syllabus Theory of Computation

Theory of Computation - Syllabus

Course Overview and Structure
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

Key Topics

  • Compiler Structure
    UN-1.1

    Analysis and Synthesis Model of Compilation, including different sub-phases within analysis and synthesis phases.

  • Compiler Concepts
    UN-1.2

    Basic concepts related to Compiler, including interpreter, simple One-Pass Compiler, preprocessor, macros, symbol table, and error handler.

  • Regular Expressions and Languages
    UN-1.3.1

    Introduction to regular expressions and languages, including equivalence with finite automata and algebraic laws.

  • Properties of Regular Languages
    UN-1.3.2

    Exploration of properties of regular languages, including the pumping lemma.

  • Minimization of Finite State Machine
    UN-1.3.3

    Techniques for minimizing finite state machines.

Key Topics

  • Context-Free Grammar
    UN-2.1.1

    Study of context-free grammar, including parse trees, derivation, and ambiguity. Normal forms of context-free grammar, such as CNF and GNF, are also explored.

  • Regular Grammars
    UN-2.1.2

    Introduction to regular grammars and their properties, including closure properties of context-free languages.

  • Proving a Language to be Non-Context-Free
    UN-2.1.3

    Techniques for proving that a language is not context-free, including pumping lemma and other methods.

  • Push Down Automata (PDA)
    UN-2.2.1

    Definition and properties of push down automata (PDA), including language of PDA and equivalence with CFGs.

  • Deterministic and Non-deterministic PDA
    UN-2.2.2

    Study of deterministic and non-deterministic push down automata, including their properties and applications.

  • Equivalence of PDA's and CFG's
    UN-2.2.3

    Exploration of the equivalence between push down automata and context-free grammars, including conversion techniques.

Key Topics

  • Turing Machines
    UN-3.1.1

    Introduction to Turing Machines, including their basic concept and computation process.

  • Variants of Turing Machines
    UN-3.1.2

    Exploration of different variants of Turing Machines, including their characteristics and applications.

  • Non-deterministic Turing Machines
    UN-3.1.3

    Study of non-deterministic Turing Machines, including their properties and differences from deterministic machines.

  • Turing Enumerable Languages
    UN-3.1.4

    Introduction to Turing Enumerable Languages, including their definition and relationship with Turing Machines.

  • Church's Thesis and Algorithm
    UN-3.2.1

    Explanation of Church's Thesis and its significance in the theory of computation, including the concept of algorithm.

  • Universal Turing Machines
    UN-3.2.2

    Study of Universal Turing Machines, including their properties and capabilities.

  • Halting Problems
    UN-3.2.3

    Discussion of the Halting Problem, including its definition, significance, and implications.

  • Turing Machines and Computers
    UN-3.2.4

    Comparison and contrast of Turing Machines and computers, including their similarities and differences.

Key Topics

  • Undecidability
    UN-4.1.1

    Study of undecidable problems and languages, including recursive and recursively enumerable languages, universal language, and unsolvable problems by Turing machines.

  • Encoding of Turing Machine
    UN-4.1.2

    Techniques for encoding Turing machines, including unrestricted grammars and Chomsky hierarchy.

  • Unsolvable Problems by Turing Machines
    UN-4.1.3

    Problems that cannot be solved by Turing machines, including Post's Correspondence Problem.

  • Computational Complexity
    UN-4.2.1

    Measuring the complexity of computational problems, including class P and class NP.

  • Intractable Problems
    UN-4.2.2

    Problems that are difficult or impossible to solve in a reasonable amount of time, including NP-complete problems.

  • NP-Completeness and Problem Reduction
    UN-4.2.3

    Techniques for reducing problems to NP-complete problems, and the implications for computational complexity.