# Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

A function $$f: A^* \to A^*$$ is regularity-preserving if, for each regular language $$L$$ of $$A^*$$, the language $$f^{-1}(L)$$ is regular. I think I have a proof, as a consequence of more general results, that the function defined by $$f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$$ is regularity-preserving. If this result is correct, could someone provide an elementary proof?

Here is a proposition for an elementary proof:

Let $$\mathcal A=(A,Q,q_0,F,\delta)$$ be a DFA for $$L$$, we want to build a DFA $$\mathcal A'=(A,Q',q_0',F',\delta')$$ for $$f^{-1}(L)$$. Intuitively, when reading a word $$u$$, $$\mathcal A'$$ will remember the state reached in $$\mathcal A$$ by $$f(u)$$, together with the action of $$u$$ on all states of $$\mathcal A$$. More formally, we take:

• $$Q'=Q\times Q^Q$$
• $$q_0'=(q_0,\mathit{id})$$
• $$F'=F\times Q^Q$$
• $$\delta_a'(p,g)=(\delta_a(g(p)),\delta_a\circ g)$$

Where $$\delta_a:Q\to Q$$ is the transition function associated with a letter $$a$$.

This ensures that after reading a word $$u$$, the first component of the state of $$\mathcal A'$$ gives the state reached by $$\mathcal A$$ on $$f(u)$$.

• @Denis how is the function g defined? Commented Apr 16, 2021 at 19:19
• @Hermann: $g$ is the second component of the current state: from any state $(p,g)$, reading letter $a$, we go to the state $(\delta_a(g(p)),\delta_a\circ g)$. Commented Apr 16, 2021 at 19:26
• I'd add that there is a simple and systematic way to show that a copyful streaming string transducer Σ* → Γ* is regularity-preserving, which takes a monoid morphism with codomain $M$ recognizing a language over Γ and yields a DFA with states $M^k$ recognizing a language over Σ ($k$ is the number of registers). The function considered here can be computed by a copyful SST with 2 registers, so if we compose this systematic construction with taking the transition monoid of a DFA, we get the set of states $(Q^Q)^2$ which is very close to Denis's solution! Commented Nov 3, 2022 at 1:07