Theory of Computation
Finite automata, regular expressions, grammars, pushdown automata, Turing machines, decidability and P vs NP, with every machine built and run in Python.
- Level
- Advanced
- Time
- About 24 hours
- Modules
- 5
- Lessons
- 15
- Exercises
- 45
The theory of computation asks what machines can and cannot do, and how much time they need. This course builds the answers from the ground up: strings and languages, finite automata and regular expressions, grammars and pushdown automata, and finally Turing machines, the halting problem and the P vs NP question.
Every idea is also code. You simulate DFAs and NFAs, convert one into the other, minimise them, compile regular expressions into automata, parse with CYK, run pushdown automata and Turing machines, and search for certificates, all in plain Python in your browser. By the end you can tell which kind of tool a problem needs, and prove when no tool can solve it.
What you will learn
- Design, simulate, convert and minimise finite automata
- Move between regular expressions, NFAs and DFAs, and prove languages non-regular
- Write context-free grammars, parse with CYK and simulate pushdown automata
- Build and run Turing machines, and explain the Church–Turing thesis
- Prove the halting problem undecidable and use reductions
- Explain P, NP and NP-completeness with certificates and brute-force search
Skills you will gain
- Automata design and simulation
- Regular expressions and Thompson's construction
- Grammars and parsing
- Turing machines and computability
- Complexity classes and reductions
Before you start
- Python: functions, loops, dictionaries, sets and recursion (the Python course)
- Basic proof ideas: sets, functions and proof by contradiction (the Discrete Mathematics course helps)
- Comfort reading short algorithms with loops and queues
Where it is used
- Lexers, regex engines and input validation
- Parsers for programming and data languages
- Protocol and hardware state machines
- Recognising undecidable and NP-hard problems in practice
Modules
Module 1: Strings and finite automata
The vocabulary of the subject, alphabets, strings and languages, and the deterministic finite automaton: how to define, run and design one, and how to combine two.
- 1
Alphabets, strings and languages Intermediate
The vocabulary of the theory of computation: alphabets, strings, the empty string, and languages as sets of strings, built and tested in Python.
- 2
Deterministic finite automata (DFA) Intermediate
A DFA reads a string one symbol at a time with a fixed, finite memory. Define one as five parts, draw its table and run it in Python.
- 3
Designing DFAs: memory, complement and product Intermediate
Design a DFA by deciding what it must remember, then build new machines from old ones: swap accepting states for the complement, and run two machines at once for intersection and union.
Module 2: Nondeterminism
NFAs with choices and ε-moves, the subset construction that turns them into DFAs, and minimisation, which finds the smallest DFA for a language.
- 1
Nondeterministic finite automata (NFA) Intermediate
An NFA may have several moves, or none, for a symbol, and ε-moves that read nothing. It accepts if any path accepts. Simulate one in Python by tracking the set of states it could be in.
- 2
From NFA to DFA: the subset construction Advanced
Every NFA can be turned into a DFA whose states are sets of NFA states. Build that DFA in Python, see why it can be exponentially larger, and why NFAs and DFAs recognise the same languages.
- 3
Minimising a DFA Advanced
Remove unreachable states, then merge states that no input can tell apart, by splitting groups until they are stable. The result is the smallest DFA for the language, and it is unique.
Module 3: Regular expressions and their limits
Regular expressions as formulas for languages, Thompson's construction that turns them into NFAs, and the pumping lemma that proves some languages are beyond any finite automaton.
- 1
Regular expressions Advanced
A regular expression describes a language with union, concatenation and star. Learn the three operations, how they relate to finite automata, and how to test membership with Python's re.fullmatch.
- 2
From regular expression to NFA: Thompson's construction Advanced
Parse a regular expression and build an ε-NFA for it piece by piece, then run the NFA to match strings. This is how fast regex engines work, and it proves that every regular expression describes a regular language.
- 3
Beyond regular: the pumping lemma Advanced
Some languages, such as aⁿbⁿ, need unlimited memory, so no finite automaton recognises them. The pumping lemma turns that intuition into a proof, and Python can search every split of a word to watch the argument work.
Module 4: Context-free languages
Grammars that generate nested structure, the CYK algorithm that decides membership by dynamic programming, and pushdown automata, finite machines with a stack.
- 1
Context-free grammars Advanced
A grammar generates a language with rewriting rules. Write grammars for aⁿbⁿ, balanced brackets and arithmetic, follow derivations and parse trees, spot ambiguity, and generate a grammar's strings in Python.
- 2
Parsing with the CYK algorithm Advanced
Decide whether a grammar generates a string with dynamic programming. Put the grammar in Chomsky normal form, fill a table of which variables produce each substring, and read the answer from the top cell.
- 3
Pushdown automata Advanced
Give a finite automaton a stack and it can count and match nesting. Simulate pushdown automata for aⁿbⁿ and balanced brackets in Python, and explore a nondeterministic one by searching its configurations.
Module 5: Computability and complexity
Turing machines, the most powerful model of computation; the halting problem and other problems no program can solve; and P, NP and NP-completeness, the limits of efficient computation.
- 1
Turing machines Advanced
A Turing machine has a finite control and an unlimited tape it can read, write and move along in both directions. Build a simulator in Python, write a machine that adds 1 to a binary number, and see why this simple model captures every computation.
- 2
Decidability and the halting problem Advanced
Some problems cannot be solved by any program at all. Learn the difference between deciding and recognising, follow Turing's diagonal argument that no program can decide whether programs halt, and see in Python why simulation alone cannot settle it.
- 3
P, NP and NP-completeness Advanced
Some problems are easy to check but seem hard to solve. Learn the classes P and NP, certificates and verifiers, why SAT is NP-complete, and what the P vs NP question asks, with subset sum and SAT in Python.
Projects
- A regular-expression engine Build a program that compiles a regular expression into a minimal DFA and uses it to match text, without the re module.
- A Turing machine laboratory Build a simulator that loads Turing machines from text files, runs them with traces and step limits, and use it to write and test several machines.
What to learn next
- Compiler Design Lexers, parsers, syntax trees, type checking, intermediate code, optimization and code generation: every phase of a compiler built and run in Python.
- Algorithms Searching, sorting, recursion, greedy choices, dynamic programming and graph algorithms, with the cost of each one counted.
- Discrete Mathematics Logic and proofs, induction, sets, functions and relations, counting, recurrences, number theory, RSA and graphs, every idea checked with Python.