This is a raw video from 2019. I've not yet had time to edit it into chunks. If you have any questions, or find any errors, please let me know on Piazza.

This lecture introduces a very important idea.

In previous years this idea has not been examined. This year it may be one of the things that allow you to score an excellent mark overall.

This is the idea of inductive definitions.

Slides 2 — 5 each give an example of this idea that we have already studied earlier in the course.

Slide 7 gives another example, implicit in our previous work, but now made explicit.

If you look back at our code for FSMs and NFA, you will see that the idea of reachability gives another example.

Slides 6, 7, 8 introduce the key concepts of soundness and completeness.

Finally, slides 9 and 10 work through some example questions on FSM, DFA, and regex. To get the most benefit from thses slides you should attempt the questions before watching this section.