Theory of Computation (CSC262) — Notes, Syllabus & Past Questions

Study of automata theory, formal languages, and the mathematical limits of computing.

Core Course7 Chapters
Chapter 1Past Questions

Basic Foundations

Review of Set Theory, Logic, Functions, Proofs, Automata, Computability and Complexity, Basic concepts of Automata Theory: Alphabets, Power of Alphabet, Kleen Closure, Strings, Languages.

View Questions
Chapter 2Past Questions

Introduction to Finite Automata

Introduction to Finite Automata and Finite State Machines, Deterministic Finite Automata (DFA), Non-Deterministic Finite Automaton (NFA), Equivalence of DFA and NFA, Subset-Construction.

View Questions
Chapter 3Past Questions

Regular Expressions

Regular Expressions, Regular Operators, Algebraic Rules, Equivalence of Regular Expression and Finite Automata, Pumping Lemma for Regular Languages, Closure Properties.

View Questions
Chapter 4Past Questions

Context Free Grammar

Context Free Grammar (CFG), Components and Use of CFG, Derivations (Bottom-up, Top-down, Leftmost, Rightmost), Parse Trees, Ambiguity, Regular Grammars, Simplification of CFG (CNF, GNF).

View Questions
Chapter 5Past Questions

Push Down Automata

Introduction to Push Down Automata (PDA), Representation and Operations, Deterministic and Non-Deterministic PDA, Acceptance by Final State and Empty Stack, Conversion between PDA and CFG.

View Questions
Chapter 6Past Questions

Turing Machines

Introduction to Turing Machines (TM), TM as Language Recognizer and Computing Function, Multiple Tracks and Tapes, Non-Deterministic TM, Restricted TMs, Church Turing Thesis, Universal Turing Machine.

View Questions
Chapter 7Past Questions

Undecidability and Intractability

Computational Complexity, Time and Space Complexity, Complexity Classes, Reducibility, Cook's Theorem, Undecidability, Post's Correspondence Problem, Halting Problem.

View Questions

Related Study Resources for Theory of Computation (CSC262)

Subject HubTheory of Computation (CSC262)Official CurriculumTheory of Computation SyllabusTU Board PapersTheory of Computation Past QuestionsSemester Directory4th Sem Subjects