Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 3 / 12J (Automata and Formal Languages)

A language $L$ satisfies the regular pumping lemma if there is an integer $p\ge 1$ such that every $w\in L$ with $|w|\ge p$ can be written $w=xyz$ with

Let a deterministic automaton for $L$ have $p$ states. During the first $p$ input symbols of an accepted word $w$ of length at least $p$, the run visits $p+1$ states, so two coincide. Write $w=xyz$ so that $y$ labels the nonempty loop between those visits and $|xy|\le p$. Traversing that loop any number of times leaves the remainder of the accepting run unchanged, giving $x{y}^{i}z\in L$ for every $i\ge 0$.

If an automaton with at most $100$ states accepted a word $w\in L$ of length $100$, the preceding loop argument would produce $x{y}^{i}z\in L$ for every $i\ge 0$, with $y\ne \epsilon$. These words have unbounded lengths and are distinct, contradicting the finiteness of $L$.

Take pumping length $p=1$. If a nonempty word $w\in \{0,1{\}}^{\ast }$, pump its first symbol; every pumped word remains in $\{0,1{\}}^{\ast }$. Otherwise write $w=u2v$ with $v\in L$. If $u\ne \epsilon$, pump the first symbol of $u$, leaving a word of the same form. If $u=\epsilon$, pump the initial $2$: deleting it leaves $v\in \{0,1{\}}^{\ast }$, while retaining one or more copies lets the last pumped $2$ serve as the separator. Thus every required pumped word belongs to $\hat{L}$.

Choose a language $L\subseteq \{0,1{\}}^{\ast }$ that is not recursively enumerable; such a language exists because there are uncountably many languages but only countably many algorithms. Form $\hat{L}$ as in part (d), which satisfies the pumping lemma.

If a grammar generated $\hat{L}$, enumerate its terminal derivations and retain precisely words of the form $2v$ with $v\in \{0,1{\}}^{\ast }$. Since such a word contains only one separator,This would enumerate $L$, a contradiction. Hence $\hat{L}$ is the required language.