Theory of Computation¶
Course Code: 23PCCE401
Institution: Cummins College of Engineering for Women (CCEW), Pune
Instructor: Sourav Kulkarni
Semester: Second Year, Semester IV — January 2025
About This Course¶
Theory of Computation (ToC) sits at the heart of computer science. It asks — and answers — the most fundamental questions about what computers can and cannot do:
- What does it mean to compute something?
- What problems can be solved mechanically, and which ones are forever beyond the reach of any machine?
- How do you characterize the difficulty of a problem? Can two very different-looking problems be shown to be fundamentally the same?
- What are the minimal resources (memory, time) needed to solve a class of problems?
This course builds a rigorous mathematical framework to answer these questions, moving from the simplest possible machines (Finite Automata) up through increasingly powerful models (Pushdown Automata, Turing Machines).
Course Details¶
| Item | Details |
|---|---|
| Lectures | 3 hours/week (~42 lectures/semester) |
| Tutorials | 1 hour/week/per group |
| In-Semester Assessment | 50 Marks |
| End-Semester Examination | 50 Marks |
| Credits | 4 |
Prerequisites¶
- Data Structures — comfort with recursive definitions, trees, and graphs.
- Discrete Mathematics & Statistics — sets, functions, relations, proof techniques (induction, contradiction).
Course Objectives¶
By the end of this course you will be able to:
- Recall and apply the mathematical concepts underpinning formal languages and machines.
- Design computational models — Finite Automata, Regular Expressions, Context-Free Grammars — for given languages.
- Convert between equivalent representations of a language (e.g. NFA ↔ DFA, Regex ↔ NFA, Grammar ↔ FA).
- Design Pushdown Automata and Turing Machines for languages beyond the reach of finite automata.
Syllabus at a Glance¶
| Unit | Topic |
|---|---|
| 0 | Motivation and Mathematical Foundations |
| 1 | Introduction to Formal Languages and Finite Automata |
| 2 | Regular Expressions and Languages |
| 3 | Context-Free Grammars and Languages |
| 4 | Pushdown Automata (coming soon) |
| 5 | Turing Machines and Computability Theory (coming soon) |
How to Use These Notes¶
These notes are an expanded version of the lecture slides. Definitions are stated formally, proofs are written out in full where the slides were compressed, and worked examples are explained step-by-step. Use the navigation on the left to jump to any topic.
Recommended Reading
These notes are a supplement, not a replacement, for the textbooks. The two classic references for this course are:
- Sipser, M. — Introduction to the Theory of Computation (3rd ed.)
- Hopcroft, Motwani & Ullman — Introduction to Automata Theory, Languages, and Computation (3rd ed.)
Disclaimer
These notes may contain errors. If you find one, please raise it with the instructor. Always cross-reference with the recommended textbooks for examination preparation.