Moore Machine

As we already covered the topics of DFA and NFA. DFA and NFA are the automata machines that take the input and do not give the output. Both DFA and NFA just check the acceptance of the given string. However, the Automata Moore Machine and Mealy also take the input and give the output. There is no final state in the Moore Machine.

Condition: For the Moore machine, there must be a dedicated path for each input from each state, like DFA.

Moore and Mealy machines take an input string (i.e., 11001) and give an output (i.e., aabbab).

• Each state of the Moore or Mealy machine gives an output. Output is denoted by the Output symbol.
• The initial state always gives an output. The remaining outputs depend on the transition function.

Important: The output of the Moore machine is always one greater than the input. If the input length is three (i.e., 011), the output length will be four (i.e., aabb). Because the initial state always gives an output without an input.

Formal Definition of Moore Machine

Moore and Mey machines accept all regular languages. Their output depends only on the machine’s current state, which is represented by the current state separated by “/.”

Moore machine can be described by 6 tuples (Q, q0, ∑, O, δ, λ) where,

• Q: a finite set of states  
• q0: initial state of machine  
• ∑: a finite set of input symbols  
• O: output alphabet  
• δ: transition function where Q × ∑ → Q  
• λ: output function where Q → O  

Moore Machine Example

Consider the following Moore Machine  

Explanation of Moore Machine Tuples

Explanation of 6 tuples (Q, q0, ∑, δ, O, λ) is given below

1. q0, q1, q2 are the states of the given Moore machine.
2.  q0 is the initial state.
3.  0,1 are the inputs (∑) values for transition.
4. The transition function is performed on input and gives a state move.
5. O is the output, where a and b are output symbols that are separated by “/” from the state symbol.
6. Output function (λ) gives the output. As in the above Moore Machine.
   • Initial state q0 gives output “a”.

• • If state q0 and input “1” are given, the state is changed to q1, and q1 will give the “b” output.
  • In the same way, if state q1 and input “1” are given, then the state changes to q2, and q2 will give the “b” output.

• • Similarly, if state q2 and input “0” are given, the state changes to q0, and q0 will give the “a” output. And so on…

Input to Output in Moore Machine

For instance, if the input “101001” is given to the above Moore machine, the output will be “abbbbab”. First, “a” of output comes without input. That’s why output is always greater than input length by 1. The remaining output comes after consuming each input. As shown in the following table.

Moore Transition Table 

As q0 gives output “a”, q1 gives output “b”, and q2 gives output “b”. Transition for each input is also covered in the DFA and NFA table. So, the Transition table for given Moore Machine is given below.

Moore Machine Question-Based Examples 

Let’s discuss more than 10 question based examples of Moore Machine

Moore Machine Example 01:  1’s Complement

Let’s design a Moore Machine that provides the first complement of any binary input. The 1’s complement operation means reversing every bit in a binary number, changing all 0’s to 1’s and all 1’s to 0’s. For example: If the input is 1010, then the output (1’s complement) is 0101.

Design of Moore Machine

To design a Moore machine for generating the 1’s complement, we use two states:

Moore Transition Table 

Explanation

• When the input bit is 0, the machine moves to q0, and the output is 1.

• When the input bit is 1, the machine moves to q1, and the output is 0.

The machine changes states according to the input bit and gives the 1’s complement as output.

Moore Machine Example Execution

Let the input be 1 0 1 1.

Final Output: 0 1 0 0

Moore Machine Example 02:  2’s Complement

To find the 2’s complement in a Moore machine, scan from LSB→MSB. Copy all bits up to and including the first 1 You see (this handles the “+1” by taking that 1 unchanged); after that first 1, output the bitwise complement (invert) of each remaining input bit. (Equivalent to: invert all bits, then add 1.)

The following table explains which states and outputs are used to construct the required Moore machine 

(So P0/P1 = “still copying until first 1”; I0/I1 = “we are in invert-phase”. Each state’s output is the transformed bit for the current input that just caused the transition into that state.)

Moore Transition Diagram 

Explanation of transitions

• While in P0 (haven’t seen a 1 yet and current input was 0), if the next input is 0 we stay in P0 and output 0 (copying 0). If next input is 1 we go to P1 and output 1 (this is the first 1 we copy — it realizes the “+1”).

• From P1 (we just emitted the first 1), on the next input we must switch to the invert phase: if next input is 0 → I0 (output 1), if next input is 1 → I1 (output 0).

• In the invert phase (I0/I1) we stay in invert-phase: the state chosen corresponds to the inverted output for the current input (so I0 outputs 1 when input is 0, I1 outputs 0 when input is 1), and transitions keep you inside I0/I1 appropriately.

Moore Transition Table

Example Working

Take the binary number 1011 (MSB→LSB). We will feed bits LSB→MSB into the machine: that stream is 1, 1, 0, 1.

Start in P0.

Outputs (LSB→MSB) = 1 0 1 0. Rewriting MSB→LSB gives 0 1 0 1, which is 0101 — the correct two’s complement of 1011.

Moore Machine Example 03: Moore Machine for Even Parity (running parity bit)

The machine outputs the running even-parity (0 = even number of 1s seen so far; 1 = odd number of 1s seen so far).
For each input bit, the machine updates its parity state and emits the parity after reading that bit.

Design of the Moore Machine

We use two states:

Moore Transition Table 

Moore Machine Example Execution

Let the input (MSB→LSB style) be 1 0 1 1. We feed bits left→right, and the machine starts in state E (even parity = 0).

Final Output (for the input stream) = 1 1 0 1
(These are the running parity bits after each input — e.g., after reading the first 1 parity is odd → 1, after reading 1 0 parity remains odd → 1, etc.)

Moore Machine Example 04: Moore Machine for Detecting “11” Sequence

This Moore machine outputs 1 whenever the input sequence ends with two consecutive 1’s, otherwise it outputs 0.
In other words, the output becomes 1 after seeing “11” at the end of the input sequence.

Design of Moore Machine

We use three states:

Moore Transition Table 

Moore Machine Example Execution

Let the input be: 1 0 1 1 1 0

Final Output: 0 0 0 1 1 0

 This machine “remembers” the last two input bits and lights up (output = 1) whenever the input ends with “11”.

Moore Machine Example 05: Moore Machine for Detecting “101” Sequence

This Moore machine outputs 1 whenever the input sequence ends with “101”, otherwise it outputs 0.

Design of Moore Machine

We use four states:

Moore Transition Table 

Moore Machine Example Execution

Input: 1 0 1 0 1 1

Final Output: 0 0 1 0 1 0

The output is 1 whenever the last three bits form “101”.

Moore Machine Example 6: Moore Machine for Detecting “111” Sequence

This Moore machine outputs 1 whenever the input ends with three consecutive 1s.

Design of Moore Machine

Moore Transition Table 

Moore Machine Example Execution

Input: 1 1 0 1 1 1 0

Final Output: 0 0 0 0 0 1 0

 Output = 1 when the last three bits are “111”.

Moore Machine Example 7: Moore Machine for Detecting “1001” Sequence

This Moore machine outputs 1 whenever the input sequence ends with “1001”.

Design of Moore Machine

Moore Transition Table 

Moore Machine Example Execution

Input: 1 0 0 1 0 0 1

Final Output: 0 0 0 1 0 0 1

The output is 1 when the sequence “1001” appears in the input.

Moore Machine Example 08: Moore Machine for Checking Binary Numbers Divisible by 3

The Moore machine reads a binary number (MSB → LSB) and, after each input bit, outputs 1 if the number read so far is divisible by 3, otherwise 0.

Design of Moore Machine

We use three states representing the remainder (mod 3) of the binary value seen so far:

Start state: q₀ (no bits read → value 0 → divisible by 3)

Moore Transition Diagram

Explanation

• When the next input bit is 0, the new remainder = (2 × old_remainder) mod 3.
• When the next input bit is 1, the new remainder = (2 × old_remainder + 1) mod 3.
• q₀ represents all numbers divisible by 3 and therefore produces output 1.
• q₁ and q₂ represent remainders 1 and 2, respectively, so their outputs are 0.

Moore Transition Table 

Moore Machine Example Execution

Let the input (MSB→LSB) be 1 1 0, which is binary 110 = 6 (decimal).
Start in q₀.

Final Output: 0 1 1

 The final bit = 1 → the number 110₂ (= 6) is divisible by 3.

Moore Machine Example 09: Moore Machine for Checking Binary Numbers Divisible by 4

The Moore machine reads a binary number (MSB → LSB) and, after each input bit, outputs 1 if the number read so far is divisible by 4, otherwise 0.

Design of Moore Machine

A binary number is divisible by 4 if and only if its last two bits are 00.
So, this machine needs to “remember” the last two input bits.

We will use four states to represent the last two bits seen so far:

Start state: q0 (no bits read yet → assume last two bits = 00).

Moore Transition Diagram

Moore Transition Table 

Explanation

• Each new input bit shifts the previous bits left and adds the new bit as the least significant bit (LSB).

• The state represents the current last two bits.

• Only q0 (last two bits = 00) produces output 1 since that’s the condition for divisibility by 4.

Moore Machine Example Execution

Let the input (MSB→LSB) be 1 0 0 → binary 100₂ = decimal 4.

Start in q0.

Final Output: 0 0 1

 The final output bit = 1, meaning 100₂ (4 in decimal) is divisible by 4.

Moore Machine Example 10: Moore Machine for Checking Binary Numbers Divisible by 5

The Moore machine reads a binary number (MSB → LSB) and, after each input bit, outputs 1 if the number read so far is divisible by 5, otherwise 0.

Design of Moore Machine

We use five states, each representing the remainder (mod 5) of the binary number read so far.

Start state: q0 (no bits read → value 0 → divisible by 5)

Moore Transition Table 

The next remainder is computed using:
new_remainder = (2 × old_remainder + input_bit) mod 5

Explanation

• Appending a 0 doubles the number, so remainder ← (2 × remainder) mod 5.

• Appending a 1 doubles and adds one, so remainder ← (2 × remainder + 1) mod 5.

• q0 produces output 1 because it represents numbers divisible by 5.

• All other states produce 0.

Moore Transition Diagram

updated soon..

Moore Machine Example Execution

Let the input (MSB→LSB) be 1 0 1 0, which is binary 1010₂ = decimal 10.
Start in q0.

Final Output: 0 0 1 1

The final output bit = 1, indicating that 1010₂ (= 10) is divisible by 5.

Moore Machine Example 11: Moore Machine for Checking Binary Numbers Divisible by 6

The Moore machine reads a binary number (MSB → LSB) and, after each input bit, outputs 1 if the number read so far is divisible by 6, otherwise 0.

Design of Moore Machine

Use six states representing the remainder (mod 6) of the binary value seen so far:

Start state: q0 (no bits read → value 0 → divisible by 6)

Transition rule:
new_remainder = (2 × old_remainder + input_bit) mod 6

Moore Transition Table 

(Each entry computed as (2*r + b) mod 6, where r is remainder for the present state and b is the input bit.)

Explanation

• Appending 0 doubles the current value: remainder ← (2 × remainder) mod 6.

• Appending 1 doubles and adds one: remainder ← (2 × remainder + 1) mod 6.

• q0 denotes divisibility by 6 and therefore emits 1; all other states emit 0.

Note: states q3 behaves like q0 under input 0 because 2×3 = 6 ≡ 0 (mod 6), and several states share similar transition patterns (this is expected from modular arithmetic).

Moore Machine Example Execution

Let the input (MSB→LSB) be 1 1 0, which is binary 110₂ = decimal 6.
Start in q0.

Final Output: 0 0 1

The final emitted bit = 1, indicating 110₂ (6) is divisible by 6.