<p>It turns out the answer is &quot;no&quot;: in [2] the authors show that a regular language <span class="math-container">$L$</span> exists with density <span class="math-container">$\rho_L(n) \leq |B|^n$</span> such that no regular language over <span class="math-container">$B$</span> has the same density; therefore, the injective rational length-preserving function cannot exist.</p>
<p>[2]: <em>Béal, Marie-Pierre; Perrin, Dominique</em>, <a href="http://dx.doi.org/10.1145/950620.950625" rel="noreferrer"><strong>On the generating sequences of regular languages on (k) symbols</strong></a>, J. ACM 50, No. 6, 955-980 (2003). <a href="https://zbmath.org/?q=an:1325.68125" rel="noreferrer">ZBL1325.68125</a>.</p>

CC BY-SA 4.0
2022-06-21T13:44:25.330Z
2022-06-21T13:44:25.330Z
Jake
<p>(This is a simpler rephrasing of an earlier question I have since deleted.)</p>
<h3>Definitions</h3>
<p>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 <em>input tape</em> and outputs any number of characters (including 0) to the <em>output tape</em>. 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.</p>
<p>A given transducer <span class="math-container">$T : A^* \rightarrow B^*$</span> induces a <em>rational relation</em> <span class="math-container">$\simeq_T$</span>, where for two words <span class="math-container">$a \in A^*, b \in B^*$</span>, we have <span class="math-container">$a \simeq_T b$</span> if and only if there is a path of <span class="math-container">$T$</span> that takes <span class="math-container">$a$</span> as input, outputs <span class="math-container">$b$</span>, and accepts.</p>
<p>A <em>rational function</em> is a rational relation that is also a partial function over <span class="math-container">$A^*$</span>; that is, for any word <span class="math-container">$a \in A^*$</span>, there is at  most a single <span class="math-container">$b \in B^*$</span> such that <span class="math-container">$a \simeq_T b$</span>. In this case we can write the rational function as <span class="math-container">$f_T$</span>, where <span class="math-container">$f_T(a) = b$</span>. Note that the domain and range of a rational function are both always regular languages.</p>
<p>A function over words is <em>length-preserving</em> if <span class="math-container">$\forall a \in A^*$</span>, <span class="math-container">$|f(a)| = |a|$</span>.</p>
<p>The <em>density</em> of a language <span class="math-container">$L$</span> is a function <span class="math-container">$\rho_L : \mathbb{N} \rightarrow \mathbb{N}$</span> where <span class="math-container">$\rho_L(n)$</span> is the number of words of length <span class="math-container">$n$</span> in <span class="math-container">$L$</span>.</p>
<h3>Question</h3>
<p>Let <span class="math-container">$A, B$</span> be alphabets. Let <span class="math-container">$L \subseteq A^*$</span> be a regular language with <span class="math-container">$\rho_L(n) \leq |B|^n$</span>. Does there always exist a rational, length-preserving, injective function <span class="math-container">$f : L \rightarrow B^*$</span> (that is total over <span class="math-container">$L$</span>)?</p>
<h3>Notes</h3>
<ul>
<li>Both conditions on <span class="math-container">$L$</span> are necessary for <span class="math-container">$f$</span> to exist: if <span class="math-container">$L$</span> is not regular, no rational function can have <span class="math-container">$L$</span> as its domain and be total over it; if <span class="math-container">$\rho_L(n) &gt; |B|^n$</span>, then <span class="math-container">$f$</span> can't possibly be injective and length-preserving. So the question is asking whether these conditions are also sufficient for <span class="math-container">$f$</span> to exist.</li>
<li>According to [1], such a rational length-preserving bijection between regular languages exists as long as there exists a regular language over <span class="math-container">$B^*$</span> with the same density as <span class="math-container">$L$</span>. So, the problem reduces to constructing a regular language <span class="math-container">$L' \subseteq B^*$</span> such that <span class="math-container">$\rho_L = \rho_{L'}$</span>, given that <span class="math-container">$\rho_L(n) \leq |B|^n$</span>.</li>
</ul>
<p>[1]: <em>Béal, Marie-Pierre; Lombardy, Sylvain; Sakarovitch, Jacques</em>, <a href="http://dx.doi.org/10.1007/11753728_9" rel="nofollow noreferrer"><strong>Conjugacy and equivalence of weighted automata and functional transducers</strong></a>, 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). <a href="https://zbmath.org/?q=an:1185.68381" rel="nofollow noreferrer">ZBL1185.68381</a>.</p>

CC BY-SA 4.0
2022-06-18T10:42:00.107Z
Just stating a few obvious things in case other users ask themselves the same question: dropping any of the hypothesis on the function (regular, injective, and length-preserving) makes the result trivial. For $f$ not regular, take any injections $f_n:\{u\in L:|u|=n\}\to |B|^n$ and $f=\bigcup_n f_n$. For $f$ not injective, take an automaton for $L$ and build the transducer that outputs $a$ at each transition, hence mapping $u$ to $a^{|u|}$. For $f$ not length-preserving, take $k$ such that $|A|\le |B|^k$ and then map distinct letters of $A$ to distinct words of length $k$ on $B$.
xavierm02
CC BY-SA 4.0
2022-06-18T10:47:54.593Z
So the only remaining way to weaken the statement to get a (possibly) easier to prove one is to ask for $A$ to have exactly $|B|^n$ words of length $n$. In this setting, we can try building an injective / surjective function $g:|B|^n\to L$ instead but I'm not sure how to do that.
xavierm02
CC BY-SA 4.0
2022-06-19T01:53:25.407Z
Do you know whether the answer is negative if you require the rational function to be computed by a deterministic transducer?
Neal Young
CC BY-SA 4.0
2022-06-19T04:04:28.777Z
@NealYoung You at least need to be able to read/output multiple characters at once: letting $A = \{x, y, z, w\}$ and $B = \{x,y\}$, the language $$L = (x(x+y+z+w))^*$$ seems to require as much, since you have to map to $$f(L) = ((x+y)(x+y))^*$$ and that seems to require reading pairs of characters at once. Not sure if that's what you're asking for though.
Jake
<automata-theory><regular-language><function>
Existence of injective length-preserving rational function to a smaller alphabet
Jake
# Existence of injective length-preserving rational function to a smaller alphabet

(Asked by: username_0 on 2022-06-10)

(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**](http://dx.doi.org/10.1007/11753728_9), 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](https://zbmath.org/?q=an:1185.68381).

**Tags:** automata-theory, regular-language, function
> **Comments:**
> **username_1**: Just stating a few obvious things in case other users ask themselves the same question: dropping any of the hypothesis on the function (regular, injective, and length-preserving) makes the result trivial. For $f$ not regular, take any injections $f_n:\{u\in L:|u|=n\}\to |B|^n$ and $f=\bigcup_n f_n$. For $f$ not injective, take an automaton for $L$ and build the transducer that outputs $a$ at each transition, hence mapping $u$ to $a^{|u|}$. For $f$ not length-preserving, take $k$ such that $|A|\le |B|^k$ and then map distinct letters of $A$ to distinct words of length $k$ on $B$.  
> **username_1**: So the only remaining way to weaken the statement to get a (possibly) easier to prove one is to ask for $A$ to have exactly $|B|^n$ words of length $n$. In this setting, we can try building an injective / surjective function $g:|B|^n\to L$ instead but I'm not sure how to do that.  
> **username_2**: Do you know whether the answer is negative if you require the rational function to be computed by a deterministic transducer?  
> **username_0**: @NealYoung You at least need to be able to read/output multiple characters at once: letting $A = \{x, y, z, w\}$ and $B = \{x,y\}$, the language $$L = (x(x+y+z+w))^*$$ seems to require as much, since you have to map to $$f(L) = ((x+y)(x+y))^*$$ and that seems to require reading pairs of characters at once. Not sure if that's what you're asking for though.  

---

## 1 answers

### Answer by username_0 on 2022-06-21. Score: 6 | Accepted answer

It turns out the answer is "no": in [2] the authors show that a regular language $L$ exists with density $\rho\_L(n) \leq |B|^n$ such that no regular language over $B$ has the same density; therefore, the injective rational length-preserving function cannot exist.

[2]: *Béal, Marie-Pierre; Perrin, Dominique*, [**On the generating sequences of regular languages on (k) symbols**](http://dx.doi.org/10.1145/950620.950625), J. ACM 50, No. 6, 955-980 (2003). [ZBL1325.68125](https://zbmath.org/?q=an:1325.68125).


---

