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.

Formal Definition of Moore Machine

Moore and mealy machines accept all regular languages. The output depends only on the current state of the machine. The output 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  

Example of Moore Machine

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

Transition table of Moore Machine

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.

 Example 01: Moore Machine for 1’s Complement

The 1’s complement operation means reversing every bit in a binary number — changing all 0s to 1s and all 1s to 0s.
For example:
If the input is 1010, then the output (1’s complement) is 0101.

Design of the Machine

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

Transition Table

Explanation

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

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

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

Example

Let the input be 1 0 1 1.

Final Output: 0 1 0 0

Example 02: Moore Machine for 2’s Complement

Idea (algorithm used):
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.)

States, meaning and outputs

We use 4 states (this encoding lets a Moore state produce a fixed output bit regardless of current input):

(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.)

Transition table

How to read this: starting state is P0 (we haven’t seen any 1 yet). On reading an input bit b the machine moves to the state indicated and that state’s output is the complemented/processed bit for the input just read.

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.

Worked example

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.