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.