6
$\begingroup$

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?

$\endgroup$

1 Answer 1

7
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ @Denis how is the function g defined? $\endgroup$ Apr 16, 2021 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, 2021 at 19:26
  • $\begingroup$ 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! $\endgroup$ Nov 3, 2022 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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