<p>Here is a proposition for an elementary proof:</p>
<p>Let <span class="math-container">$\mathcal A=(A,Q,q_0,F,\delta)$</span> be a DFA for <span class="math-container">$L$</span>, we want to build a DFA  <span class="math-container">$\mathcal A'=(A,Q',q_0',F',\delta')$</span> for <span class="math-container">$f^{-1}(L)$</span>. Intuitively, when reading a word <span class="math-container">$u$</span>, <span class="math-container">$\mathcal A'$</span> will remember the state reached in <span class="math-container">$\mathcal A$</span> by <span class="math-container">$f(u)$</span>, together with the action of <span class="math-container">$u$</span> on all states of <span class="math-container">$\mathcal A$</span>. More formally, we take:</p>
<ul>
<li><span class="math-container">$Q'=Q\times Q^Q$</span></li>
<li><span class="math-container">$q_0'=(q_0,\mathit{id})$</span></li>
<li><span class="math-container">$F'=F\times Q^Q$</span></li>
<li><span class="math-container">$\delta_a'(p,g)=(\delta_a(g(p)),\delta_a\circ g)$</span></li>
</ul>
<p>Where <span class="math-container">$\delta_a:Q\to Q$</span> is the transition function associated with a letter <span class="math-container">$a$</span>.</p>
<p>This ensures that after reading a word <span class="math-container">$u$</span>, the first component of the state of <span class="math-container">$\mathcal A'$</span> gives the state reached by <span class="math-container">$\mathcal A$</span> on <span class="math-container">$f(u)$</span>.</p>

CC BY-SA 4.0
2021-04-16T19:19:45.323Z
@Denis how is the function g defined?
Hermann Gruber
CC BY-SA 4.0
2021-04-16T19:26:31.863Z
@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
CC BY-SA 4.0
2022-11-03T01:07:37.157Z
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!
Lê Thành Dũng 'Tito' Nguyễn
CC BY-SA 4.0
2021-04-15T22:02:49.317Z
2021-04-16T12:32:05.527Z
2021-04-16T12:32:05.527Z
Denis
<p>A function <span class="math-container">$f: A^* \to A^*$</span> is <em>regularity-preserving</em> if, for each regular language <span class="math-container">$L$</span> of <span class="math-container">$A^*$</span>, the language <span class="math-container">$f^{-1}(L)$</span> is regular. I think I have a proof, as a consequence of more general results, that the function defined by
<span class="math-container">$$
f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)
$$</span>
is regularity-preserving. If this result is correct, could someone provide an elementary proof?</p>

<automata-theory><regular-language>
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?
J.-E. Pin
# 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?

(Asked by: username_0 on 2021-04-15)

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?

**Tags:** automata-theory, regular-language


---

## 1 answers

### Answer by username_1 on 2021-04-15. Score: 7 | Accepted 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)$.

> **Comments:**
> **username_2**: @username_1 how is the function g defined?  
> **username_1**: @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)$.  
> **username_3**: 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 username_1's solution!  

---

