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,Σ,q0,Δ,δ,λ)(Q, \Sigma, q_0, \Delta, \delta, \lambda):

QQ: This is a set of states.

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

q0q_0: This is the initial state.

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

δ\delta: This is a transition function, that is: Q×ΣQQ \times \Sigma \to Q

λ\lambda: This is an output function, that is: QΔ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:

g ENTRY q0/x q0/x ENTRY->q0/x q1/y q1/y q0/x->q1/y i q1/y->q0/x j
An example format of a Moore machine.

In the machine above, the transition on input ii will give an output yy from the state q0q_0. Moreover, from q1q_1 a transition on input jj will provide an output xx.

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

Example

Suppose we have the following Moore machine:

g ENTRY q0/a q0/a ENTRY->q0/a q0/a->q0/a 0 q1/b q1/b q0/a->q1/b 1 q1/b->q0/a 1 q2/a q2/a q1/b->q2/a 0 q2/a->q0/a 0 q2/a->q1/b 1
An example Moore machine.

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

Transitions explanation

  • Our Moore machine starts from q0q_0. Without consuming any input, it will produce an aa.
g ENTRY q0/a q0/a ENTRY->q0/a q0/a->q0/a 0 q1/b q1/b q0/a->q1/b 1 q1/b->q0/a 1 q2/a q2/a q1/b->q2/a 0 q2/a->q0/a 0 q2/a->q1/b 1
"a" is produced without consuming input
  • The first input character is 11. Hence, we move to q1q_1 and output a bb. Our output string is abab.
g ENTRY q0/a q0/a ENTRY->q0/a q1/b q1/b q1/b->q0/a 1 q2/a q2/a q1/b->q2/a 0 q0/a->q1/b 1 q0/a->q0/a 0 q2/a->q1/b 1 q2/a->q0/a 0
"b" is produced by transition q0 to q1 on "1"
  • For the next 11, we move to q0q_0, which outputs an aa. The output string becomes abaaba.
g ENTRY q0/a q0/a ENTRY->q0/a q0/a->q0/a 0 q1/b q1/b q0/a->q1/b 1 q1/b->q0/a 1 q2/a q2/a q1/b->q2/a 0 q2/a->q0/a 0 q2/a->q1/b 1
"a" is produced by transition q1 to q0 on "1"
  • The next 00 gives another aa. The output string becomes abaaabaa.
g ENTRY q0/a q0/a ENTRY->q0/a q0/a->q0/a 0 q1/b q1/b q0/a->q1/b 1 q1/b->q0/a 1 q2/a q2/a q1/b->q2/a 0 q2/a->q0/a 0 q2/a->q1/b 1
"a" is produced by transition q0 to q0 on "0"
  • The last 11 takes us to q1q_1 and produces a bb. The final output string is abaababaab.
g ENTRY q0/a q0/a ENTRY->q0/a q1/b q1/b q1/b->q0/a 1 q2/a q2/a q1/b->q2/a 0 q0/a->q1/b 1 q0/a->q0/a 0 q2/a->q1/b 1 q2/a->q0/a 0
"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
RELATED COURSES

View all Courses

Keep Exploring