A question on regular sets

Question

In the end of the Abstract of the paper Minsky and Papert - Unrecognizable Sets of Numbers, the authors write "…for every infinite regular set $A$ there is a nonregular set $A'$ for which $$ \lvert\pi_A(n)-\pi_{A'}(n)\rvert\leq 1\text{",} $$ where $\pi_A(n)$ is the counting function for $A$. But I don't find a reference in the paper. Also I want to know if the following statement is true or not: "…for every infinite nonregular set $B$ there is a regular set $B'$ for which $$ \lvert\pi_B(n)-\pi_{B'}(n)\rvert\leq 1\text{."} $$ If I understand right the "regular set" in this paper means "automatic set".

Answer 1

The second question has a negative answer. The asymptotic behavior of $\pi_B(n)$ and $\pi_{B'}(n)$ would be the same, and if $\pi_B(n)$ satisfies any of the criteria for non-regularity on page 283 of the paper by Minski and Papert, then $\pi_{B'}(n)$ would satisfy the same, and thus, cannot be regular.

For the first question, the relevant portion of the paper is Section 5, titled "Impossibility of a Converse".

Answer 2

An alternative answer to the second question, using very little information about regular languages, just that there are only countably many of them: Partition $\mathbb N-\{0,1\}$ into infinitely many infinite sets $S_n$. List all the regular languages as $(C_n:n\in\mathbb N)$. Let $B$ be any language such that $|\pi_B(n)-\pi_{C_n}(n)|>1$ forall $n\in S_n$; such a $B$ can be constructed by induction on $k$, putting into $B$, at step $k$, an appropriate number of strings of length $k$. Then no regular language $B'$ has $|\pi_B(n)-\pi_{B'}(n)|\leq1$ for all (or even for all but finitely many) $n$.