mealy machine in ocaml

I want to take composition of two Mealy machines and two finite state transducers. How to represent Me开发者_开发百科aly machine/transducer in ocaml?

What's the problem with Nicollet's answer to your previous question ? Just add an output : 'state * 'letter -> 'output member to your record, and you're done.

The type you have chosen in your own reply is not adequate.

type ('state,'letter) mealy = {
  initial    : 'state ;
  final      : 'state -> bool ;
  transition : 'letter  -> 'state -> 'letter -> 'state ;
}

Indeed, your transition will not produce an output but will use it to know which state you will reach. In mathematical words, you provide a transition function of type $(I,Q,O) \rightarrow Q$ instead of $(I,Q) \rightarrow (O,Q)$. Curryfication allows you to write $I \rightarrow Q \rightarrow (O,Q)$ but you cannot unfold the last couple type. Consequently your composition is erroneous since you introduced a d that does not exist.

You have two solutions from the automata solution in this post:

1. adding an output function as Gasche have already proposed
2. changing the type of the transition function into a correct one as 'state -> 'letter -> ('letter * 'state) for example.

Therefore you will be able to provide a composition function.

You can study the python implementation here of Mealy transducers in the package tulip. Note that Moore machines are strictly causal Mealy machines, for details please refer to this book (most authors get it wrong, which is why I mention it here. You can verify that a Moore machine was initially indeed defined so by referring to the original paper by Moore).

When it comes to composition, things get very tricky. If you mean cascade synchronous composition, then the result can be readily computed, because there is no feedback connection. But if by “composition” you refer to feedback composition, then you need to select semantics. For example, with synchronous-reactive semantics, the result of the composition is defined by the fixed point solution for each time step (see the book cited above for pointers on the subject).

The fixed point solution is needed because if both transducers are Mealy, then they may both be non-strictly causal (i.e., current output can depend on current input). In contrast, a Moore machine is strictly causal (any Mealy machine that is strictly causal is a Moore machine, but for no non-strictly causal Mealy machine does there exist an equivalent Moore machine). So composing a Moore machine with a Mealy machine does not require a fixed point computation to simulate the result.