Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 4 / 4H (Automata and Formal Languages)

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

Let $K\subseteq \mathbb{N}$ be the undecidable set denoted $\mathbb{K}$ in the question. The language satisfies the pumping lemma for regular languages with pumping length one. For any nonempty $s\in L$, write $s=xyz$ with $x=\epsilon$, $y$ its first symbol, and $z$ the remaining suffix.

If $s\in b^{\ast }$, then $x{y}^{i}z\in b^{\ast }$ for every $i\ge 0$. Otherwise $s=wa{b}^n$ for some $n\in K$. If the chosen first symbol lies in $w$, pumping it preserves the same final suffix $a{b}^n$. If $w=\epsilon$, then $s=a{b}^n$: pumping down gives $b^n\in b^{\ast }$, while every positive pump gives $a^i{b}^n$ and all but its last $a$ can be absorbed into $w$. Thus every sufficiently long word has a valid pumping decomposition.

Nevertheless, if $L$ were regular language, closure under intersection would makeregular. A finite automaton deciding this unary language would decide whether $n\in K$ by running it on $a{b}^n$, contradicting the halting problem. ThereforeThis is a nonregular language satisfying the pumping lemma.