Theory of computation
Finite state machines and Mealy machines, sets, regular expressions, BNF, Reverse Polish notation, then the limits of computation: intractable problems, the Halting problem and Turing machines, with a robot run by a state machine.
Start in the simulator- A6.1 Finite state machines States, transitions and accepting states; state transition diagrams and tables; tracing an FSM and running one from a…
- A6.2 Mealy machines: FSMs with output Output on every transition, tracing a Mealy machine, and a search, approach and stop controller for the robot.
- A6.3 Sets Set notation and comprehension, finite and countably infinite sets, cardinality, Cartesian product, subsets, union,…
- A6.4 Regular expressions and regular languages The metacharacters, matching in Python, the link between regexes and FSMs, and what makes a language regular.
- A6.5 Backus-Naur Form and syntax diagrams Production rules, syntax diagrams, a grammar for robot programs, recursive descent, and why BNF can describe what a…
- A6.6 Reverse Polish notation Infix and postfix, converting both ways, evaluating RPN with a stack, and the shunting-yard algorithm.
- A6.7 Limits of computation: tractable and intractable problems How complexity and hardware limit computation, tractable and intractable problems, and a heuristic route for the robot.
- A6.8 Computable problems and the Halting problem Non-computable problems, the Halting problem and why it cannot be solved, and what step limits can and cannot tell you.
- A6.9 Turing machines Tape, head, states and transition functions; tracing a Turing machine; the universal Turing machine and why it matters.
- A6.10 Project: the mission robot Validate a mission with a regular expression, carry it out with a Mealy machine, and report with sets.