Theory of Computation
Formal languages, automata theory, regular expressions, context-free grammars, Turing machines, decidability, and computational complexity.
Instructor: Tushar R. Mahore
Term: AY 2022–23
Location: Sipna College of Engineering & Technology, Amravati
Course Overview
A theoretical foundation course exploring the mathematical limits of computation — what problems can and cannot be solved by algorithms, and how efficiently.
Topics Covered
- Finite Automata (DFA, NFA) and regular languages
- Regular expressions and their equivalence with finite automata
- Closure properties of regular languages; Pumping Lemma
- Context-Free Grammars (CFG) and Pushdown Automata (PDA)
- Chomsky Normal Form, CYK parsing
- Turing Machines: variants, Church-Turing thesis
- Decidability: halting problem, Rice’s theorem
- Reducibility and undecidability
- Introduction to complexity classes: P, NP, NP-complete
Tools
JFLAP (automata simulation)
Materials
Course materials will be uploaded here. Contact mahoretushar@gmail.com for resources.