Moore Machine Examples

A Moore Machine is a type of finite state machine (FSM) where the output depends only on the current state, not on the input. This means that each state has a fixed output, and the output changes only when the machine transitions to a different state.

Structure of a Moore Machine

A Moore Machine is formally represented as a 6-tuple:

M=(Q,Σ,Δ,δ,q0,λ)

Where:

• Q → Finite set of states
• Σ (Sigma) → Input alphabet
• Δ (Delta) → Output alphabet
• δ (delta) → Transition function (Q × Σ → Q)
• q₀ → Initial state (starting state)
• λ (lambda) → Output function (Q → Δ)

Working of a Moore Machine

• The machine starts in an initial state (q₀).
• It reads the input symbols one by one.
• Based on the input, it moves from one state to another (state transition).
• The output is produced by the state itself, not by the input.
• The output changes only when the state changes.

In this lecture, we will explore some examples of Automata Moore Machines. 

Moore Machine Example 1:  1’s Complement

Design a Moore machine to generate 1’s complement of a given binary number.

Solution

According to the first complement, if the given input is “1”, then the output will be “0”. And if the input is “0”, then the output will be “1”.

For the First complement, there should be at least three states.

• One state is the start state.
• The 2^nd state is to accept “1’s” as input and produce output as “0”.
• The 3^rd state will accept “0’s” as input and produce output as “1”.

Hence, the final Moore machine of given example 1 will be,

For instance, take one binary number 111001, then

Thus, we get 0000110 as the 1’s complement of 111001; we can neglect the initial 0, and the output is 000110, which is the 1’s complement of 111001.

Important: The output for a Moore machine is greater than the input in length by 1. Because the start state always gives an output without consuming an input.

Transition table

The Transition table of the constructed Moore Machine is given below

Thus Moore machine 6 tuples {Q, q0, ∑, O, δ, λ} are explained below where

• Q = {q0, q1, q2},
• q0 is the initial state
• ∑ = {0, 1},
• O = {0, 1}. The transition table shows the
• The remaining two tuples ( δ and λ functions) are shown in the transition table 

Moore Machine Example 2:  2’s Complement

Design a Moore machine to generate the 2nd complement of a given binary number.

Solution

Automata Moore Machine, for 2nd complement of a given binary number, is given below

For Example: 

• Start with the binary number (0101)

• Find the 1’s complement (invert all bits), which becomes1010

• Add 1 to the 1’s complement to find the 2nd Complement, which is 1011

1010 (1’s complement) +    1 (we are adding 1) ——– 1011 ← This is the 2’s complement

So, the 2nd complement for input 0101 is 1011.

Result: if you give 0101 as input the Moore machine produce 1011 which is the result of 2nd complement

Transition table

The Transition Table for the example (generate the 2nd complement) is given below

Moore Machine Example 3:  Print “a” whenever the sequence “01” is encountered

Construct an Automata Moore Machine that prints “a” whenever the sequence “01” is encountered in any input binary string.

Solution

Moore automata machine, for the given example, is given below

Transition Table

The Transition Table for give example (prints “a” whenever the sequence “01” is encountered) is given below

Moore Machine Example 4: Respective outputs

For the following Moore machine, the input alphabet is {a,b} and the output alphabet is {0,1}.

Run the following input sequences and find the respective outputs

I) aabab
II) abbb
III) ababb

Solution

Moore automata machine, for the given example, is given below

Moore Machine Example 05: Count the occurrences  of “a’s”

Construct a Moore Machine that takes all the strings of a’s and b’s as input and counts the number of a’s in the input string in terms of 1. Where

input Σ = {a,b},  and output △ = {0,1}

Solution

Moore automata machine, for the given example to counts the number of a’s in the input string in terms of 1, is given below

Transition Table

The Transition Table for the given example (counts the number of a’s in the input string in terms of 1) is given below

Moore Machine Example 06:  Count occurrences of “abb”

Design a Moore machine that counts the occurrences of the sequence “abb” In any input string over {a,b}

input Σ = {a,b}, output △ = {0,1}

Solution

Moore automata machine, to count the occurrences of the sequence “abb” In any input string , is given below

Transition Table

The transition table provides a count of the occurrences of the sequence “abb” in any given input string.

Moore Machine Example 07:  Count Occurrences of “0101”

Design a Moore machine that counts the occurrences of the sequence “0101” In any input string over {a,b}

Input Σ = {0,1}, Output △ = {0,1}

Solution

Moore automata machine, to counts the occurrences of the sequence “0101”, is given below

Transition Table

The Transition Table for give example (counts the occurrences of the sequence “0101”) is given below

Moore Machine Example 08:  Specific substrings outputs

Design a Moore machine that takes a set of all strings over {0,1} and gives

• “A” as output if input ends with “10”
• “B” as output if input ends with “11”
• Otherwise gives C as output.

Input Σ = {0,1},  Output △ = {A,B,C}

Solution

Moore automata machine, for the given example, is given below

Transition Table

The Transition Table for given example given below

Moore Machine Example 09:  Specific substrings outputs

Design a Moore machine for a binary input sequence such that if it has a

• Substring 101, the machine output A,
• If the input has a substring 110, its output is B;
• Otherwise, it outputs C.

Input Σ = {0,1},  Output △ = {A,B,C}

Solution

Moore automata machine, for the given example, is given below

Transition Table

The Transition Table for give example is given below

Moore Machine Example 10:  Generate the remainder after dividing a number by 3

Design a Moore Machine to generate the remainder after dividing a number by 3 (modulus of 3) in binary

over Σ = {0,1}, △ = {0,1,2}

Solution

Moore automata machine, to generate the remainder after dividing a number by 3 (modulus of 3), is given below

Transition Table

The Transition Table for given example (generate the remainder after dividing a number by 3 (modulus of 3)) is given below

Moore Machine Example 11:  Generate the remainder after dividing a number by 4

Design a Moore Machine to generate the remainder after dividing a number by 4 (modulus of 4) in binary

over Σ = {0,1}, △ = {0,1,2,3}

Solution

Automata Moore Machine, to generate the remainder after dividing a number by 4 (modulus of 4), is given below

The Transition Table for give example (generate the remainder after dividing a number by 4 (modulus of 4)) is given below

Moore Machine Example 12:  Generate the remainder after dividing a number by 5

Design a Moore Machine to generate the remainder after dividing a number by 5 (modulus of 5) in binary

over Σ = {0,1}, △ = {0,1,2,3,4}

Solution

Moore automata machine, to generate the remainder after dividing a number by 5 (modulus of 5), is given below

Transition Table

The Transition Table for give example ( to generate the remainder after dividing a number by 5 (modulus of 5)) is given below

Moore vs. Mealy Machine

 Applications of Moore Machine

Here are some common application of Moore Machine in TOC

• Digital circuit design

• Traffic light control systems

• Vending machines

• Sequence detectors

• Communication protocol controllers

• Elevator control systems

Advantages of Moore Machine

Here are some advantages of Moore Machine in TOC

• Stable and predictable outputs

• Easier to debug and simulate

• Suitable for hardware implementation

 Disadvantages of Moore Machine

Here are the main disadvantages of the Moore Machine in TOC

• May require more states than Mealy machines for the same task

• Slightly slower response because output changes only after state transitions