Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 4 / 4H / a

LetIntersect it with the regular languageEvery word of $R$ contains exactly two copies of $b$. If it is a proper power, its exponent must therefore be two and its root must contain one $b$. HenceThis language is not regular: if $p$ were a pumping length, pumping any nonempty substring among the first $p$ copies of $a$ in $a^{p}b{a}^{p}b$ would change only its first $a$-block. Since regular languages are closed under intersection,This is the proper-power language is not regular.

This language is recognized by the parity-counting deterministic finite automaton with four statesThe initial state is $(0,0)$ and the only accepting state is $(1,0)$. Reading $a$ leaves the state unchanged, reading $b$ toggles $p_b$, and reading $c$ toggles $p_c$. The state therefore records exactly the parities of the numbers of $b$'s and $c$'s. Thus

Use the bounded-run deterministic finite automaton with statesState $q_j$ records that the current suffix consists of exactly $j$ consecutive zeros. Every $q_0,\dots ,q_7$ is accepting; $q_{\mathrm{dead}}$ is rejecting. Reading $1$ sends every accepting state to $q_0$, while reading $0$ sends $q_j$ to $q_{j+1}$ for $j<7$ and sends $q_7$ to $q_{\mathrm{dead}}$. The dead state loops on both symbols. This finite automaton accepts exactly the words with no run of eight zeros, so