Course Information
Prerequisites
Textbook
Theory of Computation: Automata, Formal Languages, Computation, and Complexity
Course Description
This course introduces mathematical models of computation and provides a theoretical foundation for understanding languages, machines and computational complexity. It covers finite automata, regular languages, context-free languages, pushdown automata, Turing machines, decidability and complexity classes.
Course Outcomes
- Understand finite automata and regular language theory.
- Design and analyze regular expressions and automata.
- Understand context-free grammars and pushdown automata.
- Analyze computational models using Turing machines.
- Understand decidability, undecidability and complexity classes.
- Apply theoretical concepts in compiler design, AI and computer science.
Course Deployment
Course Modules
Module 1: Finite Automata and Regular Languages
Topics Covered
- Introduction to Theory of Computation
- Deterministic and nondeterministic finite automata
- Regular expressions and regular languages
- Minimization of finite automata
- Closure properties and pumping lemma
Learning Resources
Module 2: Context-Free Languages, Grammars and Pushdown Automata
Topics Covered
- Context-free grammars and languages
- Grammar simplification and normal forms
- Ambiguity and closure properties of CFLs
- Pushdown automata
Learning Resources
Module 3: Turing Machines, Computability and Complexity
Topics Covered
- Turing machines and computational models
- Variants of Turing machines
- Recursive and recursively enumerable languages
- Decidability and undecidability
- Complexity classes P, NP and NP-Complete problems
Learning Resources
- Introduction to Turing Machines
- TM as Function Computer
- Variants of Turing Machines
- Computational Complexity of TMs
- Universal Turing Machine
- Turing-Recognizable Languages
- Recursive and Recursively Enumerable Languages
- Decidability and Undecidability
- Complexity Classes (P, NP, NP-Complete)
- Rice’s Theorem