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,
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 becomes
1010
-
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