We now modify an FA so it will produce "output".  Such abstract machines are often referred to as transducers. There are two well-understood types of transducers, as follows.

Start with an ordinary FA, but remove final states:

For each transition, also specify a character to be "output" when the transition is taken:

For this mealy machine, the output vocabulary consists of 0’s or 1’s; they could be anything.

Run the machine:   input: aab             output: 101

Again, start with a FA without final states, but specify a character to be output whenever a state (including the start state) is entered:

Q: Can we construct a Mealy machine that has the same input/output behavior as a given Moore machine (assuming that we ignore the first character of the Moore machine, which is always the same), and vice-versa? In other words, does Moore = Mealy ?

A: Yes, and it’s not too hard to prove (see the book)

Here's an example of a Mealy machine that does something useful:

input: a binary number (in reverse order) e.g. 1011 (read in reverse order = 13₁₀)
output: if you reverse it, you get (reversed input) + 1

Run it on 1011:
 

Reverse of output: 1110 = 14₁₀  !!

We know that "real" computers are not abstract automata; they are built out of "hardware" components:

• a clock, which imposes a time sequence on electronic events within the computer according to "clock cycles" at time t = 1, 2, 3, …
• wires (or lines) which connect the hardware components. during any clock cycle, a wire will either have a current (denoting a 1) or not (denoting a 0)
• gates: AND, OR, NAND, XOR etc., which combine 0’s and 1’s in particular ways, and a DELAY circuit, which delays transmission of a line value for one clock cycle

2.  input: each clock cycle, it will be either a 0 or a 1
3.  output: each clock cycle, 0 or 1
4.  we can arrange that, initially, there will be a 1 on wire S as shown

We define the "state" of this machine to be "carry" if the value on "wire S" is 1, "no carry", otherwise. The reason for these names will soon become evident. Clearly, our machine will have only two states, and will start in state "carry".  A new state will be computed on each clock cycle as a result of the circuitry.

Now, let’s describe the Mealy-machine behavior of our hardware machine:

Schematically:

The hardware circuit implements the "incrementer" FA!

A larger circuit (with more delays) will have states which depend on values on more wires; hence more states. But the analysis of the circuit will be the same.

Synthesis: putting a circuit together from the FA description, is deferred to another course!