Syllabus

BSc CSIT · Semester IV

Theory of Computation syllabus

Official TU syllabus for Theory of Computation (CSC262): 7 units, 121 topics, 3 credit hours. Every unit links to its notes and solved questions.

1

Basic Foundations

3h · 4 Q
  • Review of Set Theory
  • Logic
  • Functions
  • Proofs
  • Automata, Computability and Complexity
  • Complexity Theory
  • Computability Theory
  • Automata Theory
  • Basic concepts of Automata Theory
  • Alphabets
  • Power of Alphabet
  • Kleen Closure Alphabet
  • Positive Closure of Alphabet
  • Strings
  • Empty String
  • Substring of a string
  • Concatenation of strings
  • Languages
  • Empty Language
Unit notes →Solved questions →
2

Introduction to Finite Automata

8h · 11 Q
  • Introduction to Finite Automata
  • Introduction of Finite State Machine
  • Deterministic Finite Automata (DFA)
  • Notations for DFA
  • Language of DFA
  • Extended Transition Function of DFA
  • Non-Deterministic Finite Automaton (NFA)
  • Notations for NFA
  • Language of NFA
  • Extended Transition
  • Equivalence of DFA and NFA
  • Subset-Construction
  • Method for reduction of NFA to DFA
  • Theorems for equivalence of Language accepted by DFA and NFA
  • Finite Automaton with Epsilon Transition (ε - NFA)
  • Notations for ε - NFA
  • Epsilon Closure of a State
  • Extended Transition Function of ε – NFA
  • Removing Epsilon Transition using the concept of Epsilon Closure
  • Equivalence of NFA and ε –NFA
  • Equivalence of DFA and ε – NFA
  • Finite State Machines with output: Moore machine and Mealy Machines
Unit notes →Solved questions →
3

Regular Expressions

6h · 13 Q
  • Regular Expressions
  • Regular Operators
  • Regular Languages and their applications
  • Algebraic Rules for Regular Expressions
  • Equivalence of Regular Expression and Finite Automata
  • Reduction of Regular Expression to ε – NFA
  • Conversion of DFA to Regular Expression
  • Properties of Regular Languages
  • Pumping Lemma
  • Application of Pumping Lemma
  • Closure Properties of Regular Languages over (Union, Intersection, Complement)
  • Minimization of Finite State Machines: Table Filling Algorithm
Unit notes →Solved questions →
4

Context Free Grammar

9h · 13 Q
  • Introduction to Context Free Grammar (CFG)
  • Components of CFG
  • Use of CFG
  • Context Free Language (CFL)
  • Types of derivations: Bottomup and Topdown approach
  • Leftmost and Rightmost
  • Language of a grammar
  • Parse tree and its construction
  • Ambiguous grammar
  • Use of parse tree to show ambiguity in grammar
  • Regular Grammars: Right Linear and Left Linear
  • Equivalence of regular grammar and finite automata
  • Simplification of CFG: Removal of Useless symbols, Nullable Symbols, and Unit Productions
  • Chomsky Normal Form (CNF)
  • Greibach Normal Form (GNF)
  • Backus-Naur Form (BNF)
  • Context Sensitive Grammar
  • Chomsky Hierarchy
  • Pumping Lemma for CFL
  • Application of Pumping Lemma
  • Closure Properties of CFL
Unit notes →Solved questions →
5

Push Down Automata

7h · 9 Q
  • Introduction to Push Down Automata (PDA)
  • Representation of PDA
  • Operations of PDA
  • Move of a PDA
  • Instantaneous Description for PDA
  • Deterministic PDA
  • Non Deterministic PDA
  • Acceptance of strings by PDA
  • Language of PDA
  • Construction of PDA by Final State
  • Construction of PDA by Empty Stack
  • Conversion of PDA by Final State to PDA accepting by Empty Stack and vice-versa
  • Conversion of CFG to PDA
  • Conversion of PDA to CFG
Unit notes →Solved questions →
6

Turing Machines

10h · 12 Q
  • Introduction to Turing Machines (TM)
  • Notations of Turing Machine
  • Language of a Turing Machine
  • Instantaneous Description for Turing Machine
  • Acceptance of a string by a Turing Machines
  • Turing Machine as a Language Recognizer
  • Turing Machine as a Computing Function
  • Turing Machine with Storage in its State
  • Turing Machine as a enumerator of stings of a language
  • Turing Machine as Subroutine
  • Turing Machine with Multiple Tracks
  • Turing Machine with Multiple Tapes
  • Equivalence of Multitape-TM and Multitrack-TM
  • Non-Deterministic Turing Machines
  • Restricted Turing Machines: With Semi-infinite Tape, Multistack Machines, Counter Machines
  • Curch Turing Thesis
  • Universal Turing Machine
  • Turing Machine and Computers
  • Encoding of Turing Machine
  • Enumerating Binary Strings
  • Codes of Turing Machine
  • Universal Turing Machine for encoding of Turing Machine
Unit notes →Solved questions →
7

Undecidability and Intractability

5h · 10 Q
  • Computational Complexity
  • Time and Space complexity of A Turing Machine
  • Intractability
  • Complexity Classes
  • Problem and its types: Absract, Decision, Optimization
  • Reducibility
  • Turing Reducible
  • Circuit Satisfiability
  • Cook's Theorem
  • Undecidability
  • Undecidable Problems: Post's Correspondence Problem, Halting Problem and its proof, Undecidable Problem about Turing Machines
Unit notes →Solved questions →

Textbooks and references

  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Pearson - Addison-Wesley.
  • Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, 2nd Edition, Prentice Hall.
  • Michael Sipser, Introduction to the Theory of Computation, 3rd Edition, Thomson Course Technology
  • Efim Kinber, Carl Smith, Theory of Computing: A Gentle introduction, Prentice-Hall.
  • John Martin, Introduction to Languages and the Theory of Computation, 3rd Edition, Tata McGraw Hill.
  • Kenneth H. Rosen, Discrete Mathematics and its Applications to Computers Science, WCB/Mc-Graw Hill.

Study CSC262 the smart way

Solved questions, flashcards & practice

Keep studying

Study CSC262

All chapters, flashcards and practice.

Important questions

See what is most likely to appear.

Past papers

Solved past questions by year.

Browse subjects

All programs and subjects.

NoteTok feed

Short explainer videos.