Theory of Computation Tutorial
Learn the Theory of Computation step by step: 59 lessons in 11 chapters on automata, regular languages, grammars, pushdown automata, Turing machines, decidability and complexity.
Start learning →
of lessons completed
Getting Started
- What Is the Theory of Computation? Learn what the theory of computation studies: abstract machines, languages, decision problems and the limits of what computers can solve, with Python examples.
- Alphabets, Strings and Languages Learn the building blocks of automata theory: alphabets, strings, length, concatenation, powers, Kleene star and operations on languages, with Python code.
- Grammars and the Chomsky Hierarchy Understand formal grammars, productions and derivations, then classify any grammar into the four Chomsky types with working Python code and examples.
- Applications of Automata See where automata are used in practice: lexical analysis, string search, protocol state machines, game logic and hardware, with runnable Python examples.
Finite Automata
- Introduction to Finite Automata and DFAs Learn the formal definition of a DFA, how to read state diagrams and transition tables, dead states and acceptance, with a runnable Python DFA simulator.
- Designing DFAs: Common Patterns Learn proven DFA design patterns: counting modulo k, substrings, the k-th symbol from the right, combined conditions and divisibility, each tested in Python.
- Nondeterministic Finite Automata and ฮต-Moves Learn nondeterministic finite automata: multiple transitions, guessing, ฮต-moves and epsilon closure, with a Python simulator that tracks sets of states.
- Converting an NFA to a DFA (Subset Construction) Learn the subset construction that converts any NFA or ฮต-NFA into an equivalent DFA, with step-by-step tables, a Python implementation and the exponential blowup.
- Operations on DFAs: Complement, Union, Concatenation, Reverse Learn how to build DFAs for the complement, union, intersection, concatenation and reversal of regular languages, with the product construction and Python code.
- Minimization of DFAs Learn how to minimize a DFA by removing unreachable states and merging equivalent states, using partition refinement and the table-filling method, with Python code.
- Mealy and Moore Machines Learn Mealy and Moore machines, finite state transducers that produce output, how they differ, how to convert between them, with a binary adder and Python code.
Regular Expressions and Languages
- Regular Expressions, Regular Grammars and Regular Languages Learn the formal definition of regular expressions, the languages they describe, algebraic identities, regular grammars and star height, with Python examples.
- From Regular Expressions to Finite Automata (Thompson's Construction) Learn how to convert any regular expression into an ฮต-NFA with Thompson's construction, then to a DFA, with diagrams and a working Python regex compiler.
- From Finite Automata to Regular Expressions: Arden's Theorem and State Elimination Learn Kleene's theorem and two methods for converting a finite automaton to a regular expression, Arden's theorem and state elimination, with Python code.
- Closure Properties and Decision Properties of Regular Languages Learn which operations keep a language regular, union, complement, intersection, reversal, homomorphism and more, plus decision algorithms for emptiness and equivalence.
- The Pumping Lemma for Regular Languages Learn the pumping lemma for regular languages, why it holds, and how to prove that a^n b^n, prime-length strings and other languages are not regular, with code.
Context-Free Grammars
- Context-Free Grammars, Derivations and Parse Trees Learn context-free grammars, leftmost and rightmost derivations, parse trees and how a grammar defines a language, with design patterns and Python code.
- Ambiguity in Context-Free Grammars and Languages Learn what makes a context-free grammar ambiguous, how to detect it, how to remove ambiguity with precedence and associativity, and what inherent ambiguity means.
- Simplifying Context-Free Grammars Learn how to simplify a context-free grammar by removing useless symbols, ฮต-productions and unit productions in the right order, with a Python implementation.
- Chomsky Normal Form and Greibach Normal Form Learn how to convert a context-free grammar to Chomsky Normal Form and Greibach Normal Form, remove left recursion and use CNF in the CYK parsing algorithm.
- Closure Properties of CFLs and the Pumping Lemma for CFLs Learn which operations keep a language context-free, why intersection and complement fail, and how to prove a language is not context-free with the pumping lemma.
Pushdown Automata
- Introduction to Pushdown Automata Meet the pushdown automaton: a finite automaton with a stack. Learn its formal definition, how a computation runs, and simulate a PDA in Python.
- PDA Acceptance and Equivalence with CFGs Compare PDA acceptance by final state and by empty stack, convert between them, and turn any context-free grammar into an equivalent PDA in Python.
- Deterministic vs Nondeterministic PDA Understand deterministic and nondeterministic pushdown automata, why NPDAs are strictly stronger, and test determinism of a PDA with Python.
- PDAs for Matching Counts: a^n b^n and Friends Design pushdown automata for languages where one block of symbols must match another: a^n b^n c^m, a^n b^m c^n, a^m b^2m and more, with Python checks.
- PDAs for Sums of Counts: a^m b^n c^(m+n) and More Design PDAs where one block equals the sum of others: a^m b^n c^(m+n), a^m b^(m+n) c^n, 0^n 1^m 2^m 3^n, m+n=p+q and a^2m c^4n d^n b^m, tested in Python.
- PDAs for Either/Or Conditions and Equal Counts Build nondeterministic PDAs that guess which condition holds (i=k or j=l, i=j or j=k) and a one-state PDA for strings with equally many a's and b's.
- PDAs for Palindromes and Reversal Languages Construct pushdown automata for even palindromes w w^R, odd palindromes, all palindromes and the marked version w c w^R. Includes runnable Python checks.
Context-Sensitive and Other Models
- Context-Sensitive Grammars and Languages Learn context-sensitive grammars: the non-contracting rule, the grammar for a^n b^n c^n, derivations, and a Python tool that classifies grammars by Chomsky type.
- Linear Bounded Automata A linear bounded automaton is a Turing machine whose tape is limited to the input. Learn how LBAs match context-sensitive languages and detect infinite loops.
- Counter Machines, Two-Stack Machines and Other Models Explore automata beyond the PDA: counter machines, two-stack machines and queue automata, and why two stacks already equal a Turing machine. Python demos included.
Turing Machines
- Turing Machines: Definition and First Examples Learn what a Turing machine is: tape, head, states and transitions. Build and trace a machine for 0^n 1^n and a binary incrementer with a Python simulator.
- Variants of Turing Machines and the Church-Turing Thesis Multi-tape, nondeterministic and other Turing machine variants all have the same power. Simulate them in Python, then meet the Church-Turing thesis and universal TMs.
- Turing Machines for Addition, Subtraction, Multiplication and Comparison Design Turing machines that add, subtract, multiply and compare unary numbers. Each construction is explained state by state and tested in a Python simulator.
- Turing Machines for Copying Data and 1's and 2's Complement Build Turing machines that copy a string and compute the 1's and 2's complement of a binary number. Marker technique, state diagrams and Python checks included.
- Turing Machines for 0^n 1^n 2^n, w w^R and w w Construct Turing machines for languages that need more than a stack: 0^n 1^n 2^n, even palindromes w w^R and the copy language ww. Python simulator and tests.
- Turing Machines for a^n b^m a^(n+m) and a^i b^j c^(i*j) Design Turing machines for languages built from sums and products of block lengths: a^n b^m a^(n+m) and a^i b^j c^k with i*j=k. Includes state design and Python tests.
Decidability and Computability
- Recursive and Recursively Enumerable Languages Understand Turing-decidable (recursive) and Turing-recognizable (recursively enumerable) languages, enumerators, closure properties and why co-RE matters, with Python.
- Countability, Diagonalization and Decidable Problems Why most languages are unrecognizable: countable and uncountable sets, Cantor's diagonal argument, and a tour of decidable problems for DFAs and CFGs in Python.
- The Halting Problem: Proof of Undecidability State and prove the halting problem is undecidable by diagonalization. See the contradiction in Python and learn why A_TM is recognizable but not decidable.
- Reductions, Rice's Theorem and the Post Correspondence Problem Prove problems undecidable by reduction from the halting problem, learn Rice's theorem on semantic properties, and explore the Post Correspondence Problem in Python.
- Computable Functions, Ackermann and the Busy Beaver Learn total and partial computable functions, primitive recursion, the mu operator, the Ackermann function and the uncomputable busy beaver function with Python.
Complexity
- Time Complexity and the Class P Measure how many steps a Turing machine takes, define DTIME and the class P, see why input size matters, and run a Python machine that counts its own steps.
- Nondeterminism and the Class NP Learn what NP means with two equivalent views, nondeterministic machines and polynomial-time verifiers, then check certificates for Subset Sum and Hamiltonian paths in Python.
- Polynomial-Time Reductions Understand polynomial-time many-one reductions, how to read A <=p B, and why reductions transfer hardness. Test Partition to Subset Sum and Clique to Independent Set.
- NP-Completeness and the Cook-Levin Theorem Define NP-hard and NP-complete, follow the idea behind the Cook-Levin theorem, then run a SAT brute-force and DPLL solver and a SAT to 3-SAT converter in Python.
- Classic NP-Complete Problems Meet the classic NP-complete problems and their reduction chain: 3-SAT, Clique, Independent Set, Vertex Cover, Hamiltonian cycle and TSP, with tested Python reductions.
- Space Complexity, PSPACE and Savitch's Theorem Learn how memory is measured on a Turing machine, the classes L, NL and PSPACE, Savitch's theorem and TQBF, with Python demos of recursive reachability and QBF.
- The Complexity Hierarchy and the P versus NP Question See how complexity classes nest, why more time buys more power (the hierarchy theorems), what P versus NP would change, and run a diagonalization demo and a feasibility table.
- Coping with NP-Hard Problems What to do when a problem is NP-hard: approximation algorithms, heuristics, special cases, parameterized algorithms and randomization, with Python vertex cover and TSP examples.
Projects
- Project: A DFA Simulator and Minimizer Build a complete finite automata toolkit in Python: a DFA simulator, union and complement, the subset construction from NFA to DFA, and a DFA minimizer you can test.
- Project: A Regular Expression Engine Build a regular expression matcher from scratch in Python: parse a regex, build an NFA with Thompson's construction, simulate it in linear time and test it against Python's re module.
- Project: A Grammar Toolkit with CNF Conversion and a CYK Parser Build a context-free grammar toolkit in Python: remove epsilon and unit rules, convert to Chomsky normal form, parse with the CYK algorithm, count parse trees and test everything.
- Project: A Turing Machine Simulator Build a Turing machine simulator that reads rules from plain text, prints step-by-step traces, decides palindromes and increments binary numbers, and searches for busy beavers.
Practice and Review
- Practice: Finite Automata and Regular Languages Worked practice problems on DFAs, regular expressions, the pumping lemma and Myhill-Nerode, with every solution checked by a Python test harness you can run and extend.
- Practice: Grammars and Pushdown Automata Practice designing context-free grammars and pushdown automata, prove languages are not context-free, and check every answer with a PDA simulator and a grammar tester.
- Practice: Turing Machines and Decidability Practice problems on designing Turing machines, classifying languages as decidable, recognizable or neither, and writing reduction proofs, with machines verified by a Python simulator.
- Practice: Complexity Problems Practice problems on P, NP, verifiers, reductions and NP-completeness proofs, with tested Python verifiers, a Hamiltonian path reduction, 2-SAT in P and pseudo-polynomial DP.
- Theory of Computation Review and Cheat Sheet A complete review of the Theory of Computation: the Chomsky hierarchy, closure and decision properties, key theorems, complexity classes, plus runnable demos of the pigeonhole argument and decision algorithms.