# A regular language derived from another

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.

Posted on Categories proxies