A regular language derived from another

Question

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.

Answer 1

In order to show that $f$ is regularity preserving, it suffices to show that $f^{-1}(U)$ is eventually periodic for $U = \{ n : n \equiv b \pmod{a} \}$, where $a$ is a prime power (here we are using the Chinese remainder theorem and the fact that the eventually periodic sets are closed under intersection).

For $f(n) = 2^n$, we consider two cases:

• If $a = 2^k$ then $f(n) \equiv 0 \pmod{a}$ for large enough $n$.

• If $a = p^k$ for an odd prime $p$, then $(2,a) = 1$, and so we can think of $2$ as an element of the multiplicative group $\mathbb{Z}_a^\times$. In particular, $2^n \bmod a$ is periodic, the period being the order of $2$ in the group.