Back to Mealy Machines

Example
1: NOT

Example 2: Vending Machine

Let's start with a simple Mealy machine that takes an input bit
string *b* and produces the output NOT(*b*).

The machine should look like this, and can be downloaded through mealyNOT.jff:

A Mealy machine that produces NOT(*b*)

As you can see, the initial state has two outgoing transitions,
one for the input "0" that produces the output "1",
and one for the input "1" that produces the output "0".
Thus, for every bit *b _{i}* of the input, this machine
produces the output NOT(

Let's step the machine through the input "101".

Initial set up

The machine is in its initial, and only, state, *q*_{0}.
The two outgoing transitions from *q*_{0} each produce
the negation of the input bit. Click **Step** to process the next
bit of the input.

Step 1

Upon processing the first bit of the input, "1", the
machine takes the transition *1* ; *0*, producing the
output "0", which is the negation of the input bit. This
transition takes the machine back to its only state, *q*_{0}.
Click **Step** to process the next bit of input.

Step 2

Upon processing the next bit of the input, "0", the
machine takes the transition *0* ; *1*, producing the
output "1", which is the negation of the input bit. This
transition takes the machine back to *q*_{0}. We have
seen that state *q*_{0} properly processes both input
bit "0" and "1", and returns the machine to *q*_{0},
showing that the machine will properly process any input bit. Click
**Step** to complete the process.

Step 3

As we can see, the machine indeed produces the negation of its input bit string.

We can also test this machine on multiple strings.

Testing the machine on multiple strings

As you can see, it produces NOT(*b*) in every instance.

You can download the file here to try it out.

(Example adapted from *Theory of Finite Automata with an
Introduction to Formal LanguagesK* by John Carroll and Darrell
Long.)

Next, let's consider a more complex machine. We shall build a vending machine that dispenses one piece of candy once enough money has been inserted, and returns the appropriate amount of change. (To see a completed version, feel free to download mealyVending.jff.)

Let *V* = ({0*c*, 5*c*, 10*c*, 15*c*},
{*n*, *d*, *q*}, {*c*_{0}, *c*_{1},
*c*_{2}, *c*_{3}, *c*_{4}},
δ, ω, 0*c*}. (See the
Mealy machine definition.)
*V* describes a vending machine that dispenses 20¢
candy bars.

Mealy machine *V*

This Mealy machine has four states, 0*c*, 5*c*, 10*c*,
and 15*c*, each describing the amount of money inserted in the
vending machine, 0¢, 5¢, 10¢, and 15¢. Its input
alphabet of *n*, *d*, and *q*, denotes the insertion
of nickels, dimes, and quarters respectively. In its output alphabet,
λ denotes the vending machine doing nothing, while *c*_{0},
*c*_{1}, *c*_{2}, *c*_{3}, and
*c*_{4}, denote the machine dispensing candy and no,
one, two, three and four nickels respectively as change.

Let's step through the input *ndq*. (That is, someone
inserted a nickel, a dime, followed by a quarter.)

No coins inserted

The machine starts at 0*c*, as it has not had any money
inserted yet. Click **Step** to insert the first nickel.

First coin (a nickel) inserted

The machine takes the transition *n* ; λ from 0*c* to
5*c*, denoting that 5¢ has been inserted. The transition
produces no output as not enough money has been inserted. Click **Step**
to insert the next coin, a dime.

Second coin (a dime) inserted

The machine takes the transition *d* ; λ from 5*c* to
15*c*, indicating that 15¢ has been accumulated. Again, the
transition produces no output as not enough money has been inserted.
Click **Step** to insert the last coin, a quarter.

Last coin (a quarter) inserted

The machine takes the transition *q* ; *c*_{4}
from 15*c* to 0*c*, back to the initial state. The
transition produces output *c*_{4}, and the vending
machine dispenses a piece of candy and four nickels. Thus, once it
has accumulated sufficient money, it dispenses a piece of candy and
the correct amount of change, just as we have described.

Let's try our vending machine out on different sets of change.

Running the vending machine on different sets of coins

As you can see, each time our vending machine accumulates
sufficient money, it dispenses a piece of candy and the appropriate
amount of change. The last two inputs, *dd* and *ddn*,
although different, produce the same output *c*_{0}.
This is because they end in different states. Effectively, for input
*ddn* the vending machine still has 5¢ in it.

The trace for input *dd*

For input *dd*, the state we end in is 0*c*, indicating
there is no extra change in the vending machine.

The trace for input *ddn*

For input *ddn*, the state we end in is 5*c*, indicating
that we still have 5¢ of change in it.