Theory of Computation
Automata are the one part of theory that is genuinely visual. These topics feed a string to a machine symbol by symbol and show which states stay alive.
Start from the beginning →13 topics you can watch now, 7 still to come.
Foundations
The vocabulary every later machine is defined in, and what a machine is actually being asked to do.
- Alphabets, Strings and LanguagesStart here. Four definitions, built one on top of the next, and the reason a language is just a set.
- Machines and RecognitionWhat it means for a machine to accept a string — states, transitions, and the one bit of memory a finite machine is allowed.
- Proof techniques: induction and contradiction
Regular languages
The simplest machines there are — finite memory, one pass, no going back.
- Running a DFAFeed a string to a three-state machine and watch it decide, one symbol at a time.
- Running an NFAThe same language, one arrow too many — watch the machine track every possibility at once.
- Regular Expressions to NFAThompson's construction: every operator has one wiring pattern, and the whole machine is those patterns nested.
- NFA → DFA by Subset ConstructionNondeterminism buys no extra power. Watch the choices get absorbed into sets of states.
- DFA MinimisationSplit states until no block can be split again, then merge what is left. The result is provably the smallest.
- The Pumping LemmaWhy aⁿbⁿ is not regular — pigeonhole finds a loop, and the loop can be pumped into a string outside the language.
Context-free languages
Add a stack, and suddenly you can count matching brackets.
- The Chomsky HierarchyFour nested classes of language, and exactly what memory each one costs you.
- Grammars, Derivations and AmbiguityBuild the same parse tree top-down, and see why one string having many derivations is harmless but two trees is not.
- Pushdown AutomataOne stack is exactly enough to match aⁿbⁿ — and exactly not enough for aⁿbⁿcⁿ.
- CNF and CYK parsing
Turing machines
Add an unbounded tape, and you have every computer ever built.
- Variants and equivalence
- The Church-Turing thesis
Decidability
The questions no machine can answer, and how we prove it.
- Decidable vs recognisable
- Reductions
- P, NP and NP-completeness
About Theory of Computation
Theory of computation asks what can be computed at all, and answers it without reference to any real computer. That sounds abstract until you notice it is the only subject that gives you genuine impossibility results — problems no amount of engineering will ever solve.
It builds by adding memory. A finite automaton has none beyond its current state, and that limit is exactly why it cannot count arbitrarily. Give it a stack and it can match nested brackets. Give it an unbounded tape and you have a Turing machine, the strongest model anyone has found. Each step up buys a specific new capability, and knowing which is which tells you what kind of tool a problem needs.
The payoff is practical more often than students expect. Regular expressions are finite automata. Parsers are pushdown automata. Knowing that a language is not regular tells you immediately that no regex will ever match it correctly, which saves a great deal of time.
What to know first
- Comfort with sets, and with the idea of a formal rule
- A willingness to treat a machine as a mathematical object rather than hardware
Where it gets used
- Recognising when a regex is the wrong tool and a parser is required
- Reasoning about what a validation rule can and cannot enforce
- Understanding why some compiler and static-analysis limits are permanent