Definition
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
A Moore machine is very similar to a Finite Automaton (FA), with a few key differences:
It has no final states.
It does not accept or reject input, instead, it generates output from input.
Lastly, Moore machines cannot have nondeterministic states.
Let's go through these points.
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.
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.
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:
|
Initial: |
Step 1: |
Step 2: |
. . . |
Final: |
|
|
|
|
. . . |
|
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
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.
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.
