Mealy Machines

Contents

Definition
Differences between a Mealy Machine and an FA

Proceed to Mealy Machine Examples

Definition

JFLAP defines a Mealy 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

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

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

Starting a new Mealy machine

Differences between a Mealy Machine and an FA

A Mealy 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 it will produce a pop-up menu that allows you to, among other things, set it to be a final state. In a Mealy machine, that option is not available.

An FA state menu

A Mealy machine state menu

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

Transition Output

A Mealy machine produces output each time it takes a transition.

Creating a Mealy machine is the same as creating an FA with the exception of creating its transitions. In a Mealy machine, each transition produces output. When you are creating a transition, two blanks appear instead of one. The first blank is for the input symbol, the second blank is for the output symbol.

Creating a transition

When the transition is created, its label will be two symbols separated by a semicolon, ";". The input symbol is to the left of the semicolon, and the output symbol is to its right.

Transtion created

Thus, when in q0 with input of "1", the machine will take the transition to q1 and produce the output "0".

With each transition producing output, the Mealy machine can produce output from an input string.

Producing Output from an Input String

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

Let's look at this simple Mealy machine, which can be downloaded through mealyNOT.jff:

A simple Mealy 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

No Nondeterminism

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

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

Mealy 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 Mealy machine.

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

View Mealy machine examples.
View Moore machines.