Automata 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 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  

Automata Moore Machine Example in TOC

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.

Input to Output in Moore Machine

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.

Transition table in Moore Machine