(This is a simpler rephrasing of an earlier question I have since deleted.)
Definitions
For this question, a finite-state transducer is like a standard NFA, except at each transition, the transducer reads any number of characters (including 0) from the input tape and outputs any number of characters (including 0) to the output tape. These two tapes need not have the same alphabet. Like an NFA, when the input tape is exhausted, the transducer can either reject or accept the input, depending on what state it ends in.
A given transducer $T : A^* \rightarrow B^*$ induces a rational relation $\simeq_T$, where for two words $a \in A^*, b \in B^*$, we have $a \simeq_T b$ if and only if there is a path of $T$ that takes $a$ as input, outputs $b$, and accepts.
A rational function is a rational relation that is also a partial function over $A^*$; that is, for any word $a \in A^*$, there is at most a single $b \in B^*$ such that $a \simeq_T b$. In this case we can write the rational function as $f_T$, where $f_T(a) = b$. Note that the domain and range of a rational function are both always regular languages.
A function over words is length-preserving if $\forall a \in A^*$, $|f(a)| = |a|$.
The density of a language $L$ is a function $\rho_L : \mathbb{N} \rightarrow \mathbb{N}$ where $\rho_L(n)$ is the number of words of length $n$ in $L$.
Question
Let $A, B$ be alphabets. Let $L \subseteq A^*$ be a regular language with $\rho_L(n) \leq |B|^n$. Does there always exist a rational, length-preserving, injective function $f : L \rightarrow B^*$ (that is total over $L$)?
Notes
- Both conditions on $L$ are necessary for $f$ to exist: if $L$ is not regular, no rational function can have $L$ as its domain and be total over it; if $\rho_L(n) > |B|^n$, then $f$ can't possibly be injective and length-preserving. So the question is asking whether these conditions are also sufficient for $f$ to exist.
- According to [1], such a rational length-preserving bijection between regular languages exists as long as there exists a regular language over $B^*$ with the same density as $L$. So, the problem reduces to constructing a regular language $L' \subseteq B^*$ such that $\rho_L = \rho_{L'}$, given that $\rho_L(n) \leq |B|^n$.
[1]: Béal, Marie-Pierre; Lombardy, Sylvain; Sakarovitch, Jacques, Conjugacy and equivalence of weighted automata and functional transducers, Grigoriev, Dima (ed.) et al., Computer science – theory and applications. First international computer science symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8–12, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34166-8/pbk). Lecture Notes in Computer Science 3967, 58-69 (2006). ZBL1185.68381.