Moore Machine Examples

In this lecture, we will explore some examples of Automata Moore Machines. During the previous lecture, we covered the topic of Moore Machines.

Example 1: Moore Machine For 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 

Example 02 –  Moore Machine 2nd 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

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

Example 03 –  Moore Machine to 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

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

Example 04 –  Moore Machine for 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

Example 05 – Moore Machine to 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

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

Example 06 –  Moore Machine to 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

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

Example 07 –  Moore Machine to 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

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

Example 08 –  Moore Machine for 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

The Transition Table for given example given below

Example 09 –  Moore Machine for 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

The Transition Table for give example is given below

Example 10 –  Moore Machine to 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

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

Example 11 –  Moore Machine to 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

Example 12 –  Moore Machine to 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

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