Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

automata
theoretical cs
fa

# What is a Moore machine?

Zainab Ilyas

### Overview

A Moore machine is a finite state machine that has an output value rather than a final state. For a given input, the machine generates a corresponding output. The output of the Moore machine depends only on the present state of the FA.

Unlike other finite automata that determine the acceptance of a particular string in a given language, Moore machines determine the output against given input.

### Formal theorem

The Moore machine is a 6 tuple machine $(Q, \Sigma, q_0, \Delta, \delta, \lambda)$:

$Q$: This is a set of states.

$\Sigma$: This is a set of input alphabets.

$q_0$: This is the initial state.

$\Delta$: This is a set of output states.

$\delta$: This is a transition function, that is: $Q \times \Sigma \to Q$

$\lambda$: This is an output function, that is: $Q \to \Delta$

Note: The output function means that for every state there is a corresponding output associated with it.

### Formation of the machine

The Moore machine forms an FA of the type:

An example format of a Moore machine.

In the machine above, the transition on input $i$ will give an output $y$ from the state $q_0$. Moreover, from $q_1$ a transition on input $j$ will provide an output $x$.

Note: If the input string is of length $n$, the output produced by a Moore machine will be of length $n+1$.

### Example

Suppose we have the following Moore machine:

An example Moore machine.

Now, we take an input string in $\Sigma \{0,1\}$ and see its output in $\Sigma \{a,b\}$. Let's take $x=1101$

#### Transitions explanation

• Our Moore machine starts from $q_0$. Without consuming any input, it will produce an $a$.
"a" is produced without consuming input
• The first input character is $1$. Hence, we move to $q_1$ and output a $b$. Our output string is $ab$.
"b" is produced by transition q0 to q1 on "1"
• For the next $1$, we move to $q_0$, which outputs an $a$. The output string becomes $aba$.
"a" is produced by transition q1 to q0 on "1"
• The next $0$ gives another $a$. The output string becomes $abaa$.
"a" is produced by transition q0 to q0 on "0"
• The last $1$ takes us to $q_1$ and produces a $b$. The final output string is $abaab$.
"b" is produced by transition q0 to q1 on "1"

#### Transition table

The transition table for the above machine will be:

 Current State Destination State for 0 Destination State for 1 Output q0 q0﻿﻿﻿ q1 a q1 q2 q0 b q2 q0 q1 a

A transition table contains all the properties of a Moore machine. As a result, it can also be used to form a Moore machine.

Note: To learn about a faster type of output generating machine, the Mealy machine, click here.

RELATED TAGS

automata
theoretical cs
fa

CONTRIBUTOR

Zainab Ilyas
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time