Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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