# 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?

## 1 Answer

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? – Hermann Gruber Apr 16 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)$. – Denis Apr 16 at 19:26