Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 4 4H a iii Solution Created 2026-09-24 Updated 2026-10-03
Use the bounded-run deterministic finite automaton with statesState records that the current suffix consists of exactly consecutive zeros. Every is accepting; is rejecting. Reading sends every accepting state to , while reading sends to for and sends to . The dead state loops on both symbols. This finite automaton accepts exactly the words with no run of eight zeros, so