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 2nd state is to accept “1’s” as input and produce output as “0”.
  • The 3rd state will accept “0’s” as input and produce output as “1”.

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

Example of Automata Moore Machine

For instance, take one binary number 111001, then

Input to output of Automata Moore Machine

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

Moore Machine Example - first Complement transition table

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

Moore Machine Example - Transition diagram of 2's Complement

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

Moore Machine Example - Transition table of 2's Complement

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

Moore Machine Example 2

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

Moore Machine Example - Transition table for Prints “a” whenever the sequence “01” occur

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}.

Moore Machine Example- find the respective outputs from transition table

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- respective sequence outputs from transition table

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

Moore Machine Example - counts the number of a's

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 Examples - Transition Table for counts the number of a's

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

Moore Machine Example - Transition Diagram for counts occurences of abb

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

Moore Machine Example - Transition Table for counts occurrences of abb

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

Moore Machine - transition diagram to find Sequence 0101

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

Moore Machine -transition table for Detecting Sequence 0101

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

Moore Machine - A as output if input ends with 10 Diagram

The Transition Table for given example given below

Moore Machine Example - A as output if input ends with 10 table

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

Moore Machine -transition diagram- output for 110, 101

The Transition Table for give example is given below

Moore Machine -transition table - output for 110, 101

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

Moore Machine Example - generate remainder after dividing a number by 3

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

Moore Machine Example Table - remainder after dividing a number by 3

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

Moore Machine Diagram - generate remainder after dividing a number by 4

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

Moore Machine Table - generate remainder after dividing a number by 4

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

Moore Machine Diagram - generate remainder after dividing a number by 5

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

Moore Machine Table - generate remainder after dividing a number by 5