<p>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$). </p>

<p>We can write this as a type declaration in Ocaml like so:</p>

<pre><code>type ('a,'b) mealy = M : 's * ('a * 's -&gt; 'b * 's) -&gt; ('a,'b) mealy
</code></pre>

<p>Then the compose operation in looks like this: </p>

<pre><code>let compose : type a b c. (a,b) mealy -&gt; (b,c) mealy -&gt; (a,c) mealy = 
  fun (M(s, f)) (M(t, g)) -&gt; 
    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')) 
    in
    M(state, trans)
</code></pre>

<p>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. </p>

CC BY-SA 4.0
2018-06-06T14:36:09.963Z
2018-06-06T14:36:09.963Z
Neel Krishnaswami
<p>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}^*$?</p>

CC BY-SA 4.0
2018-06-26T06:23:56.570Z
I am afraid it is not a research level question.
J.-E. Pin
<automata-theory><fsm>
"Combining" two mealy machines
rexloxrix
# "Combining" two mealy machines

(Asked by: username_0 on 2018-06-05)

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

**Tags:** automata-theory, fsm

> **Comments:**
> **username_1**: I am afraid it is not a research level question.  

---

## 1 answers

### Answer by username_2 on 2018-06-06. Score: 4

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')) 
    in
    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.


---

