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}^*$?


closed as off-topic by J.-E. Pin, Jan Johannsen, András Salamon, Joshua Grochow, Aryeh Jul 4 '18 at 11:00

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – J.-E. Pin, Jan Johannsen, András Salamon, Joshua Grochow, Aryeh
If this question can be reworded to fit the rules in the help center, please edit the question.

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


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