Injective map, that maps context-free languages to regular languages Let $\Sigma \neq \emptyset$ be an alphabet. Is there an injective map $f: \Sigma^* \rightarrow \Sigma^*$ such that for every context-free language $L \subseteq \Sigma^*$ the set $f(L)$ is a regular language?
At first I thought there cannot be such a map, but I could not proof it and now I am starting to think that such a map could exist, but look very complicated.
 A: Yes there is.  This is a case where it is easier to prove it as a corollary of something that looks stronger, but the strengthening makes it easier to see the wood for trees:

Theorem: Let $X$ be a countable set and $\mathcal K$ be a countable subset of $\mathcal P(X)$. Then there is a bijection $f:X\to\mathbb N$ such that for every $A\in \mathcal K$  the set $\{\mathtt 1^{f(x)}\mid x\in A\}$ is a regular language in $\{\mathtt 1\}^*$.

Your property will then follow with $X=\Sigma^*$ and $\mathcal K$ being the class of context-free languages.
Proof. We will construct $f$ in phases, following an enumeration of $\mathcal K$. After each step we will know the value of $f(x)$ every $x\in Y$ where $Y$ is a finite subset of $X$, and $X\setminus Y$ will be partitioned into finitely many infinite subsets $Z_1, Z_2, \ldots Z_n$ such that we have decided that each $Z_i$ will map bijectively to a particular infinitie arithmetic progression in $\mathbb N$. Initially $Y=\varnothing$ and $Z_1=X$ will map to $\{1,2,3\ldots\}$.
In a generic phase we'll be considering some $A$ in $\mathcal K$. For each of the $Z_i$s, consider the sets $Z_i\cap A$ and $Z_i\setminus A$.
If $Z_i\cap A$ is finite, we add it to $Y$, assigning its elements to the first numbers in the arithmetic progression for $Z_i$. The $Z_i$ for the next phase will be $Z_1\setminus A$.
If $Z_i\setminus A$ is finite, do the same thing with $Z_i\cap A$ and $Z_i\setminus A$ swapped.
If $Z_i\cap A$ and $Z_i\setminus A$ are both infinite, split $Z_i$ in two $Z$s for the next phase, and split the arithmetic progression similarly into two disjoint progression with double the step size.
After this step we know that $f(A)$ is the union of $f(Y\cap A)$ (which is finite because $Y$ is) with finitely many infinite arithmetic progressions. Thus $\{\mathtt 1^{f(x)}\mid x\in A\}$ is regular.
Without loss of generality we can assume that $\mathcal K$ contains all singletons, and then every $x\in X$ will have assigned a value eventually, namely at the latest when we consider $\{x\}\in\mathcal K$. So $f$ is well defined.
Um, not so fast? Is it obvious that $f$ is surjective? In principle I think one could imagine cases where some numbers are never assigned if the above procedure is followed strictly. But we can fix that by adding an extra step to each of the phases: The smallest $m\in\mathbb N$ that is not yet in the image of $f$ must be the first element in one of the $Z_i$ progressions. Assign this $m$ as the image of one of the (infinitely many) elements of $Z_i$. In this way we can make sure that $f$ will be surjective.

Note that the $f$ constructed in this way is not necessarily computable, because it may be undecidable whether $Z_i\cap A$ is finite or not.
A: Well, if the alphabet $\Sigma$ is at most countably infinite (as is often the case), then both the set $\mathcal C$ of context-free languages over $\Sigma$ and the set $\mathcal R$ of regular languages over $\Sigma$ are countably infinite. Therefore there is a bijection $g : \mathcal C \rightarrow \mathcal R$. Then, for a given language $L$, just say that $f(L) = g(L)$ if $L$ is context-free, and $f(L) = L$ otherwise. Then $f$ is injective and has the desired property.
Constructing such an $f$ explicitly seems not just complicated, but impossible (i.e., I don't think there exists a computable $f$ satisfying your requirements).
Edit: Sorry, I think I misunderstood your question. I thought $f$ had to be a function mapping languages to languages. If it maps strings to strings, what I wrote doesn't apply, of course.
