 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ii/paper-4/4h/a/iii/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

q_{0}, q_{1}, \dots, q_{7}, q_{dead} .

State

q_{j}

records that the current suffix consists of exactly

j

consecutive zeros. Every

q_{0}, \dots, q_{7}

is accepting;

q_{dead}

is rejecting. Reading

1

sends every accepting state to

q_{0}

0

sends

q_{j}

q_{j + 1}

for

j < 7

and sends

q_{7}

q_{dead}

. The dead state loops on both symbols. This finite automaton accepts exactly the words with no run of eight zeros, so

the language is regular .

 New to topics? Read the docs here!