Given a Mealy machine $M$, is it possible to construct another Mealy machine $M'$ that generates the reverse outputs from the reverse inputs, and if so, how?

That is, for each string $s$, $M(s) = t$ iff $M'(s') = t'$, where $s'$ is $s$ reversed and $t'$ is $t$ reversed.

For example, if $M(``abcd")$ is $``efgh"$ then $M'(``dcba")$ should be $``hgfe"$.


That's not possible in general. The classical Mealy machine definition requires the Mealy machine to accept infinite-length input strings and produce infinite-length output strings while reading the input. You can't reverse an infinite-length input string and can't reverse an infinite-length output stream, since there is no last letter in the unreversed string that you could put as first letter in the reversed string.

So for your question to make sense, you would first need to change the definition to allow the Mealy machine to have missing successors for some state/input combination, so that an input word ends at a well-defined position. Then, you would need to assume that the automaton eventually has a missing transition for every possible input word. This excludes all cycles in the automaton.

If we have this, then there is only a finite number of different input strings. If $M'$ is actually well-defined, then it is possible to build such a Mealy machine. But $M'$ may not be well-defined. For example if $M(\textit{abcd}) = \textit{efgh}$ and $M(\textit{cd}) = \textit{he}$, then we have $M'(\textit{dcba})=\textit{hgfe}$ and $M'(\textit{dc}) = \textit{eh}$. By the definition of Mealy machine, this also means however that $M'(\textit{d})=\textit{h}$ and $M'(\textit{d}) = \textit{e}$, which is a contradiction.

  • $\begingroup$ I don't get it. Why does it need to accept infinite strings? Given a Mealy machine as a diagram, I can feed it any finite string and get a finite output. My question is limited to finite strings. $\endgroup$
    – Ron Inbar
    Nov 6 '17 at 19:26
  • $\begingroup$ @RonInbar A Mealy machine needs to have exactly one successor state for every current state/next input combination. So for every infinite-length input string, it needs to induce a corresponding infinite-length output string. Even if you only use finite-length strings as input, the definition of a Mealy machine still allows these infinite-length input strings. Note that the example where M' is not defined does not use this argument. $\endgroup$
    – DCTLib
    Nov 10 '17 at 14:46

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.