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?

Question

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?

Answer 1

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)$.