= Solution
Let $K$ be the <diagonal halting set>, which is <undecidable>. The pumping argument below actually holds for every subset $K\subseteq\mathbb N$; nonregularity needs the stated convention, or at least a set of exponents whose unary language is nonregular.
The <pumping lemma for regular languages> holds with <pumping length> one. For an accepted nonempty word, pump its first symbol. A word containing only $1$s remains in $1^*$ even if that symbol is deleted. If there is a zero and a nonempty prefix before its last zero, pumping the first symbol leaves the last zero and its following $n\in K$ ones unchanged. If the word is $01^n$, pumping its initial zero produces $0^i1^n$; this is accepted for $i\geq1$, and for $i=0$ it belongs to $1^*$. In every case the pumped substring is nonempty and lies in the first position.
If $L$ were a <regular language>, closure under intersection would make
$$
L\cap01^*=\{01^n:n\in K\}
$$
regular. A <finite-state automaton> for this intersection would decide membership of $n$ in the <diagonal halting set> by reading $01^n$, a contradiction. Thus \b[$L$ satisfies the pumping lemma but is not regular], under the usual meaning of $\mathbb K$. If $K$ were arbitrary, the printed conclusion would be false, for example for $K=\mathbb N$.
Back to article page
