 Solution

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

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

This language is recognized by the parity-counting deterministic finite automaton with four states

Q = {(p_{b}, p_{c}) : p_{b}, p_{c} \in Z_{2}} .

The initial state is

(0, 0)

and the only accepting state is

(1, 0)

a

leaves the state unchanged, reading

b

toggles

p_{b}

c

toggles

p_{c}

. The state therefore records exactly the parities of the numbers of

b

's and

c

's. Thus

the language is regular .

 New to topics? Read the docs here!