Back to Moore Machines

Example
1: NOT

Example 2: Halving a Binary Number

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

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

A Moore machine that produces NOT(*b*)

As you can see, this machine has three states, with *q*_{0}
producing no output, *q*_{1} producing the output "1",
and *q*_{2} producing the output "0".

The initial state, *q*_{0} produces no output as, in
this case, we do not want the machine to produce an output if it is
not given any input. (We adopt the output
convention that the initial state produces output even if there
is no input.) As you can see, if we do not want the initial state to
produce output, we can use a "dummy state," like *q*_{0}.

There are two other states, *q*_{1} that produces the
output "0", and *q*_{2} that produces the
output "1". Any outgoing transition on the input "0"
goes to *q*_{2}, so the input bit "0" always
produces the output bit "1". Similarly, any outgoing
transition on the input "1" goes to *q*_{1},
so the input bit "1" always produces the output bit "0".

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

Initial set up

The machine is in its initial state, *q*_{0}. It does
not produce any output because the output assigned to that state is
λ, or the empty string. 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 to *q*_{1}. At *q*_{1},
it produces the output bit "0", which is the negation of
the input bit. If we examine *q*_{0}, we can see that it
will always correctly handle the first bit of intput. The state
itself produces no output. If the first bit of input is "1",
it will take the transition to *q*_{1}, that will
produce the output of "0". On the other hand, if the first
bit of input is "0", it will take the transition to *q*_{2},
producing the output of "1". Click **Step** to process
the next bit of the input.

Step 2

Upon processing the next bit of the input, "0", the
machine takes the transition to *q*_{2}. At *q*_{2},
it produces the output bit "1", which is the negation of
the input bit. If we examine all the incoming transitions to *q*_{2}
we will see that, from any state, the input of "0" will
cause the machine to enter *q*_{2}. Thus, from any
state, the input bit "0" will create the output of "1".
Click **Step** to process the next bit of the input.

Step 3

On processing the last bit of the input, "1", the
machine takes the transition to *q*_{1}. At *q*_{1},
it produces the output bit "0", which is the negation of
the input bit. Examining all incoming transitions to *q*_{1},
we will see that, very much like *q*_{2}, from any
state, the input of "1" will cause the machine to enter *q*_{1}.
Therfore, from any state, the input bit of "1" will create
the output of "0". Thus, we have seen that the machine will
produce the negation of any bit string.

We can also test this machine on multiple input strings.

Testing the machine on multiple strings

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

Next, let's discuss a slightly more complex machine that halves a binary number, truncating any decimal places. It should be noted that halving a binary number merely involves dropping the least significant bit, or shifting the number right by one bit. However, we will make this a little more complicated by dictating that the machine will receive input starting from the most significant bit to the least significant bit, or from left to right. Thus, this would require the machine to remember the most recent two bits of input.

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

A Moore machine that halves binary numbers

Let's take a look at the machine. There are four possible permutations of two consecutive bits, 00, 01, 10, and 11, and each is represented by a state in the machine. For instance, the state 01 means that the most recent input bit was 1, and the input bit before that was 0. Each state produces the output equivalent to the second-most recent input bit, and stores the most recent bit to relay that information to the next state (where it will become the second-most recent input bit).

Let's step through the input "101".

Initial set up

We chose state 00 as the initial state as it is the only state that accurately represents the binary number before any bits have been processed. In other words, adding two 0's as the most significan bits in a binary number will not change the value of the number. Similarly, the output of state 00, "0", added as the most significant bit of the entire output, will not change its value.

The state produces the output of "0". Click **Step**
to process the next bit.

First bit, "1", processed

The machine has processed the first bit of input, "1", taking transition 1 from state 00 to state 01. State 01 then produces the output "0". Although this state, state 01, produces the same output as the initial state, state 00, it is different because it remembers that the most recent input bit is "1". Thus, it takes different transitions than the initial state for the same input.

Notice that all outgoing transitions from this state, state 01 go
to states that produce an output of "1". This is equivalent
to the function of shifting the bits right by one, as the machine's
output is the second-most recent bit. Click **Step** to process
the next bit.

Second bit, "0", processed

The machine processes the next bit of input, "0", and
takes transition 0 to state 10. State 10 then produces the output
"1", which corresponds to the previous input bit, "1".
This state now remembers that the most recent input bit was "0",
and all outgoing transitions are to states which have the output "0".
Click **Step** to process the next bit.

Last bit, "1", processed

The machine processes the last bit of input, "1", and takes transition 1 to state 01. It produces the output "0", completing the output. Although the most recent, and last, input bit was "1", this is ignored, effectively shifting all the bits to the right by one. This concludes the machines process of dividing a binary number by two.

Let's try our machine out on different numbers.

Running the machine on different numbers

As you can see, the machine produces the correct results in each instance. You might notice that in every instance, the output starts with "00", which is unnecessarly, even if it does not change the number. This is because the machine starts in state 00, which produces the output "0" even if there is no input. We could have avoided the this unnecessary "0" by adding a dummy initial state as we did in the previous example.

The second "0" is due to the fact that all the outgoing transitions from state 00, lead to states that have the output "0". Regardless of the first bit of the input, the first bit of output is "0" because the number is divided by two, that would shift all bits to the right by one. This "0" is also necessary for single-bit numbers such as 0 and 1.