Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 3 / 4I (Automata and Formal Languages)

A DFA consists of finite $Q$, alphabet $\Sigma$, transition $\delta$, initial $q_0$, and accepting set $F$. Extend by $\hat{\delta }(q,ϵ)=q$ and $\hat{\delta }(q,wa)=\delta (\hat{\delta }(q,w),a)$. It accepts $\{w:\hat{\delta }(q_0,w)\in F\}$; a language is regular if some DFA accepts it.

The pumping lemma for regular languages says that for some $N$, every accepted word $w$ of length at least $N$ factors $w=xyz$ with $|xy|\le N$, $|y|>0$, and $x{y}^{k}z$ accepted for every $k\ge 0$.

Regular. A DFA need only remember the current run length of $b$'s, using states $0,\dots ,99$ and a rejecting sink at 100.

Since $w_i=(ab{)}^{2^{i-1}}$, the language is $\{(ab{)}^{2^j}:j\ge 0\}$. If it were regular, pumping a sufficiently long member would alter its number of $ab$ blocks by a fixed positive amount, producing non-powers of two for some pumping exponent. Hence it is not regular.