This is similar to a previous question I asked, but doesn’t seem aminable to the same technique. Given a regular language $A$, show the following language is regular:

$$

{x|exists y ; |y| = 2^{|x|} and ; xy in A}

$$

I’m aware of the notion of regularity preserving functions, and that it would suffice to show that $f(x) = 2^x$ satisfies the property that for an ultimately periodic set $U$, $f^{-1}(U) = {m|f(m) in U}$ is ultimately periodic. I’m struggling to $f$ has this property, but the book from which this comes implies a solution not using this is possible. It appears to be looking for a construction.

I can see that by repeated application of the idea behind the Pumping Lemma, if $A$ has DFL with $k$ states, that for any $x$ with $|x| geq k$ then

$$

exists y ; |y| = 2^{|x|} and ; xy in A implies exists y ; |y| leq k ; and ; xy in A

$$

But this doesn’t give anything going in the opposite direction, that shows that some suitably short $y$ guarantees the existence of a $y$ of the required length.

Any help in solving this, or hint at how to progress would be very helpful.