Moore Machines


Differences between a Moore Machine and an FA

Output Convention
Proceed to Moore Machine Examples


JFLAP defines a Moore machine M as the sextuple M = (Q, Σ, Γ, δ, ω, qs) where

Q is a finite set of states {qi | i is a nonnegative integer}
Σ is the finite input alphabet
Γ is the finite output alphabet
δ is the transition function, δ : Q × Σ Q
ω denotes the output function, ω : Q Γ
qs (is a member of Q) is the initial state

Moore machines are different than Mealy machines in the output function, ω. In a Moore machine, output is produced by its states, while in a Mealy machine, output is produced by its transitions.

To start a new Moore machine, select the Moore Machine option from the main menu.

Starting a new Moore machine

Differences between a Moore Machine and an FA

A Moore machine is very similar to a Finite Automaton (FA), with a few key differences:

Let's go through these points.

No Final State

In an FA, when you have the Attribute Editor tool selected (you may do so by clicking the button), right-clicking on a state will produce a pop-up menu that allows you to, among other things, set it to be a final state. In a Moore machine, that option is not available.

An FA state menu

A Moore machine state menu

A Moore machine does not have final states because it does not accept or reject input. Instead, each state produces output, which will be described below.

State Output

A Moore machine produces output when it is at a state.

Creating a Moore machine is the same as creating an FA with the exception of creating its states. In a Moore machine, each state produces output. When you are creating a state, a popup dialog box appears that prompts you for the output of the state.

Entering the state output

Type the state output in the dialog box and hit click OK. (If you click Cancel, the state will still be created, it will just have an empty string as its output.) When the state is created, its output will be show in its top right hand corner:

State created

Thus, when the machine is in state q0, it will produce an output of "1". To change the state output, click on the state using the Arrow tool , and enter the new output in the dialog box.

With each state producing output, the Moore machine can produce output from an input string.

Producing Output from an Input String

Instead of accepting or rejecting input, a Moore machine produces output from an input string.

Let's look at this simple Moore machine (which is provided in mooreNOT.jff):

A simple Moore machine

When we select the menu option Input : Step... and enter your input, we get a display similar to that of an FA, except with another piece of tape below the input tape. This displays the output of the machine at the current step.

The output display

At each step. The output tape updates itself to display the total output that has been produced so far:


Step 1:

Step 2:

. . .


. . .

The menu option Input : Fast Run... works similarly, with the output being displayed in a tape under the input tape:

Fast run output display

Similarly, when we select Input : Multiple Run, output is displayed in the Result column.

Multiple run output display

No Nondeterminism

As Moore machines map an input to a unique output, nondeterminism cannot exist in a Moore machine. Although we still will be able to build a Moore machine that has nondeterminism, we will not be able to run input on it.

For instance, let's modify our machine slightly to make:

Moore machine with nondeterminism

We we try to run it on an input, with Input : Step..., Input : Fast Run..., or Input : Multiple Run..., we will get an error message asking us to remove the nondeterministic states:

Select Test : Highlight Nondeterminism to view the nondterministic states. Remove the nondeterminism in order to be able to run input on the Moore machine.

Output Convention

In JFLAP, we adopt the output convention that the machine produces the output associated with the start state when it is turned on. (The alternate view is that the machine does not produce output until the first symbol of input is read.) If we wish to use the alternate view for a machine, we may just add a start state with the empty string as its output, like the machine described above.

This concludes our brief tutorial on Moore machines. Thanks for listening!

View Moore machine examples.
View Mealy machines.