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

  • $\begingroup$ @Denis how is the function g defined? $\endgroup$ – Hermann Gruber Apr 16 at 19:19
  • 1
    $\begingroup$ @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)$. $\endgroup$ – Denis Apr 16 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.