Moore Machine

For Complete YouTube Video: Click Here

In this class, We discuss Moore Machine.

The reader should have prior knowledge of finite automata. Click Here.

Moore Machine: Moore machine is a finite state machine with an output value given on state.

Take an example and understand the Moore machine.

The below diagram is a Moore machine example.

Moore Machine 1.1

On state q0, we have an output symbol 1.

If we are in state q0, this machine will display 1.

Take an input string 01010.

The output displayed by the Moore machine for the given input string 01010 is 111011.

We start from the initial state q0. The machine will display output one because we are in state q0.

After taking the first input symbol 0, we move to state q1. so the machine will display 1.

Similarly, after processing the input string, we get the output 111011.

The below diagram shows the transition table for the Moore machine. We have an output mentioned in each state.

Moore Machine 1.2

Example 1: Construct a Moore machine that takes a set of all strings over an alphabet (a,b) as input and counts no of occurrences of ab.

The below diagram shows the Moore machine to count the occurrences of ab.

Moore Machine 1.3

On state q0, if we find the input symbol b, we more to state q0.

On state q0, if we find the input symbol a, we move to state q1.

We are moving one step because we need to find the occurrences of ab.

On state q1, if we find the input symbol b, we have to move to state q2.

On state q2, we are displaying output symbol 1.

Whenever we are in state q2, we find an occurrence of ab. so we display 1.

The count of occurrences of ab is obtained by the number of ones in the output.

The remaining logic can easily understand by the reader. Similar to finite automata.

A six tuple represents a Moore machine.

{Q,q0, Σ, O,δ,λ}

Q Finite set of states.

q0 Initial state.

Σ Finite set of input symbols.

O output alphabet.

δ Transition function Q X Σ – Q

λ Output Function Q – O