2
$\begingroup$

et $A$ be a finite alphabet. Let $A^*$ denote the language of all words in $A$, and $\epsilon$ the empty word. Let $\rho : A^* \to A^*$ denote the "reverting" map, that transforms $a_1a_2\ldots a_n$ into $a_na_{n-1} \ldots a_1$. I consider here a simplified version of finite automata on $A$. Thus I define an Ewan automaton on $A$ as a triple $(S,tr,s_0)$ where $S$ is a finite set of states, tr is a “transition” map $S \times A \to S$ and $s_0$ is an element of $S$. For such an automaton, there is a unique map $F : A^{*} \to S$ satisfying for any $w\in A^*$ and $a\in A$,

$ (*) F(\epsilon)=s_0, \ F(wa)=tr(F(w),a) $

Now let $f$ be a map $A^{*} \to X$ where $X$ is a finite set. If “f can be computed using the automaton”, i.e. if we can find $S,tr,s_0,F$ satisfying (*) as above, and a map $\phi : S \to X$ such that $f=\phi \circ F$, I say that $f$ is automatic.

Given such an $f$, one may consider the dual map $f^{d}=f \circ \rho $.

My question is : is $f$ is automatic, must $f^{d}$ be automatic also ?

On the examples I’ve seen the answer is yes, although the automaton computing $f^{d}$ can be much larger than the one computing $f$.

1 Answers 1

2

Yes. It suffices to show that $f: A^* \to X$ is automatic iff $f^{-1}(x)$ is regular for all $x \in X$: If $f^{-1}(x)$ is regular then so is ${(f^d)}^{-1}(x) = \rho(f^{-1}(x))$ since the regular languages are closed under the mirror operation.

If $f: A^* \to X$ is computed by an automaton $(S,\mathrm{tr}, s_0)$ via $\phi: S \to X$ then you get an automaton recognizing $f^{-1}(x)$ by marking $\phi^{-1}(x)$ as accepting states.

If for each of the (finitely many) $x \in X$ there is an automaton $M_x = (S_x, tr_x, s_{0,x}, F_x)$ recognizing $f^{-1}(x)$ ($F_x$ is the set of accepting states) you can construct an automaton computing $f$ by running all the $M_x$ in parallel and setting $\phi(s) := x$ if $s\in F_x$.