Theory of Computation (TOC)

What computers can and cannot do: alphabets and languages, DFA and NFA (with subset construction), regular expressions, the pumping lemma and minimisation, context-free grammars and pushdown automata, Turing machines, decidability and P vs NP — every machine built and run as a small Python simulator.

1. 01Theory of Computation Basics — Alphabets, Strings, Languages and the Chomsky HierarchyThe vocabulary of TOC — alphabets, strings, length, concatenation, Kleene star and languages — why we study machines that recognise languages, and the Chomsky hierarchy mapping regular, context-free, context-sensitive and recursively enumerable languages to their machines.
2. 02Deterministic Finite Automata (DFA) — Design, Transition Tables and a Python SimulatorLearn DFAs properly: the 5-tuple definition, state diagrams and transition tables, designing DFAs for "ends with", "contains", "divisible by 3" and counting problems, a reusable Python DFA simulator, product construction and real-world state machines.
3. 03NFA and ε-NFA — Nondeterminism, Epsilon Moves and NFA to DFA Conversion (Subset Construction)What nondeterminism means, NFAs and ε-NFAs, why they're easier to design, how to simulate them by tracking sets of states, and the subset construction that converts any NFA into an equivalent DFA — implemented step by step in Python with a worked exam example.
4. 04Regular Expressions and Regular Languages — Regex to Automata, Closure Properties and Practical RegexFormal regular expressions (union, concatenation, star), writing regex for typical exam languages, Thompson's construction from regex to ε-NFA, closure properties of regular languages, identities, and how textbook regex relates to the regex in Python, Java and JavaScript.
5. 05Non-Regular Languages and DFA Minimisation — The Pumping Lemma, Myhill–Nerode and Table FillingHow to prove a language is NOT regular with the pumping lemma (aⁿbⁿ, palindromes, prime lengths), the intuition behind it, Myhill–Nerode distinguishability, and minimising a DFA with the partition / table-filling method — implemented in Python.
6. 06Context-Free Grammars and Pushdown Automata — Derivations, Parse Trees, Ambiguity, CNF, CYK and Stack MachinesGrammars that describe nested structure: CFG definitions, derivations and parse trees, ambiguity (the dangling-else and expression grammars), Chomsky Normal Form, the CYK membership algorithm, and pushdown automata for aⁿbⁿ and balanced brackets — all runnable in Python.
7. 07Turing Machines — The Model of Every Computer, Designing TMs, Variants and the Church–Turing ThesisThe Turing machine explained simply: tape, head, states and transitions, a Python simulator running machines for binary increment and aⁿbⁿcⁿ, why multi-tape and nondeterministic variants add no power, universal Turing machines, and the Church–Turing thesis.
8. 08Decidability and Complexity — The Halting Problem, Reductions, Rice's Theorem, P vs NP and NP-CompletenessThe limits of computation: decidable and undecidable problems, the halting problem proof (with a Python-style paradox), reductions, Rice's theorem, then complexity — P, NP, NP-complete, NP-hard, SAT and why P vs NP matters — with a brute-force SAT solver and verifier in Python.