Formal Languages and Automata Theory

The route

Lessons are in the order that makes each one easier than the last. Each unit ends with a short quiz.

1. 0/3

   Unit 1

   Mathematical Preliminaries: Alphabets, Strings and Languages

   Before we build machines, we agree on exactly what they read — symbols, strings and the sets of strings we call languages.
   1. Introduction to the Theory of ComputationFree Before you ask what a computer can do fast, ask what any machine can do at all. 11 min
   3. Alphabets, Strings and Operations on Strings Every input any machine will ever read is built from a handful of symbols, joined in a row. 12 min
   4. Formal Languages and Operations on Languages A language is just a chosen set of strings, and every computing problem can be dressed up as one. 13 min
   5. Unit 1 quiz6 questions on this unit 8 min
2. 0/6

   Unit 2 Full plan

   Finite Automata

   A machine with no memory except the state it is in — and yet it powers every keypad lock, vending machine and text search you have used.
   1. Deterministic Finite Automata (DFA) A machine whose only memory is the room it is standing in, and it is still useful everywhere. 13 min
   2. Design of Deterministic Finite Automata Designing a DFA is deciding what is worth remembering, and forgetting everything else. 13 min
   3. Nondeterministic Finite Automata (NFA and ε-NFA) Let the machine guess, follow every guess at once, and accept if any guess works out. 13 min
   4. Conversion of NFA to DFA (Subset Construction) Replace "which state am I in?" with "which states could I be in?" and the guessing disappears. 14 min
   5. Minimisation of Deterministic Finite Automata Two states that can never be told apart by any input are really one state wearing two name tags. 13 min
   6. Finite Automata with Output: Moore and Mealy Machines Some machines do more than say yes or no; they talk back after every step. 13 min
   7. Unit 2 quiz12 questions on this unit 15 min
3. 0/5

   Unit 3 Full plan

   Regular Expressions and Regular Languages

   One-line patterns that describe exactly what finite automata can recognise, and a lemma that proves what they cannot.
   1. Regular Expressions and Regular Sets A one-line pattern that names a whole infinite language, and the algebra that lets you simplify it. 12 min
   2. Conversion of Regular Expressions to Finite Automata Snap together tiny machines like Lego bricks, one per symbol and one per operator, and the whole pattern becomes an automaton. 12 min
   3. Conversion of Finite Automata to Regular Expressions Remove the states one by one, writing what each one did onto the arrows, until only the pattern is left. 13 min
   4. The Pumping Lemma for Regular Languages A machine with p rooms that walks p steps must enter some room twice, and that one fact proves which languages no automaton can recognise. 14 min
   5. Closure and Decision Properties of Regular Languages Combine two regular languages almost any way you like and the result is still regular, and that fact is a tool for proofs. 13 min
   6. Unit 3 quiz8 questions on this unit 10 min
4. 0/5

   Unit 4 Full plan

   Formal Grammars and Context-Free Languages

   Rules that generate sentences — the same rules that let a compiler understand nested brackets and arithmetic.
   1. Formal Grammars and the Chomsky Hierarchy Automata check sentences; grammars write them, and four kinds of grammar sort every language into a ladder. 13 min
   2. Context-Free Grammars, Derivations and Parse Trees The same sentence can be built in many orders, but a parse tree records only what was built, not when. 12 min
   3. Ambiguity in Context-Free Grammars When one sentence has two parse trees, a calculator can honestly disagree with itself about 2 + 3 × 4. 12 min
   4. Simplification of Context-Free Grammars Before a grammar can be put into a standard shape, clear out the dead rules, the empty rules and the rules that only rename. 13 min
   5. Normal Forms: Chomsky Normal Form and Greibach Normal Form Every context-free grammar can be rewritten so that each rule has the same tidy shape, and tidy shapes make proofs and parsers simple. 14 min
   6. Unit 4 quiz8 questions on this unit 10 min
5. 0/4

   Unit 5 Full plan

   Pushdown Automata and Properties of Context-Free Languages

   Give a finite automaton a stack of plates to remember with, and it can suddenly count and match brackets.
   1. Pushdown Automata (PDA) Give a finite automaton a stack of plates and it can suddenly count, match and remember. 13 min
   2. Acceptance by Final State and by Empty Stack Two ways for a PDA to say yes, one guess about the middle of a palindrome, and the price of being deterministic. 13 min
   3. Equivalence of Pushdown Automata and Context-Free Grammars A grammar that generates and a machine that recognises turn out to be two descriptions of the same languages. 13 min
   4. The Pumping Lemma and Closure Properties of Context-Free Languages Every long enough string in a context-free language has two pieces that can be pumped together, and that is how we prove some languages are beyond any grammar. 14 min
   5. Unit 5 quiz6 questions on this unit 8 min
6. 0/4

   Unit 6 Full plan

   Turing Machines, Decidability and Complexity

   The simplest machine that can compute anything computable — and the questions no machine can ever answer.
   1. Turing Machines (TM) An endless strip of paper, a pencil with an eraser and a short rulebook turn out to be enough to compute anything a computer can. 14 min
   2. Variants of Turing Machines and the Church–Turing Thesis Add tapes, add tracks, add guessing — the Turing machine shrugs and computes exactly the same things. 14 min
   3. Decidability and the Halting Problem Some questions have no algorithm at all — not a slow one, not a clever one, none — and we can prove it. 14 min
   4. Introduction to Computational Complexity: P, NP, NP-Complete and NP-Hard Decidable is not the same as doable — some problems are easy to check yet seem impossibly slow to solve. 13 min
   5. Unit 6 quiz7 questions on this unit 9 min

Practise and remember