How could you combine two mealy machines, the first one $M_1$ has as input $\sum_{1}^*$ and as output $\sum_{2}^*$, the second machine $M_2$ uses the output $\sum_{2}^*$ as the input and outputs $\sum_{3}^*$. So what is the resulting $M_2◦M_1(w)$ machine, where $w$ is a word from $\sum_{1}^*$?

  • 1
    $\begingroup$ I am afraid it is not a research level question. $\endgroup$ – J.-E. Pin Jun 26 '18 at 6:23

A Mealy machine consists of a state set $S$, an initial state $s \in S$, and a transition function $A \times S \to B \times S$ (which takes as input a letter from the alphabet $A$ and a current state $S$, and produces an output letter drawn from $B$ and an updated state from $S$).

We can write this as a type declaration in Ocaml like so:

type ('a,'b) mealy = M : 's * ('a * 's -> 'b * 's) -> ('a,'b) mealy

Then the compose operation in looks like this:

let compose : type a b c. (a,b) mealy -> (b,c) mealy -> (a,c) mealy = 
  fun (M(s, f)) (M(t, g)) -> 
    let state = (s,t) in 
    let trans (a, (s, t)) = 
      let (b, s') = f(a, s) in
      let (c, t') = g(b, t) in 
      (c, (s',t')) 
    M(state, trans)

So the state of the composite machine are the products of the two state sets, and the new initial state is the pairing of the two initial states, and the composite transition function feeds the input to the first transition function and uses its output as the input to the second transition function.

| cite | improve this answer | |

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