Question

Justify that there can be the equivalent Mealy machine for any Moore machine by suitable example.

Answer 1

An equivalent Mealy machine can be constructed for any Moore machine by associating the output with the transition between states rather than the state itself. This involves redefining the output function to depend on both the current state and the input symbol.

Answer 2

To justify that an equivalent Mealy machine can be constructed for any Moore machine, we need to show a general construction method and illustrate it with an example.

Understanding Moore and Mealy Machines

1. Moore Machine: The output is associated with the state. When the machine enters a state, it produces an output.

   • Formal Definition: $M_{Moore} = (Q, \Sigma, O, \delta, \lambda_{Moore}, q_0)$
     • $Q$: finite set of states
     • $\Sigma$: finite set of input symbols
     • $O$: finite set of output symbols
     • $\delta: Q \times \Sigma \to Q$: transition function
     • $\lambda_{Moore}: Q \to O$: output function (maps states to output symbols)
     • $q_0 \in Q$: initial state
   • A Moore machine produces an initial output $\lambda_{Moore}(q_0)$ even before processing any input.

2. Mealy Machine: The output is associated with the transition (or input and current state). When the machine moves from one state to another based on an input, it produces an output.

   • Formal Definition: $M_{Mealy} = (Q, \Sigma, O, \delta, \lambda_{Mealy}, q_0)$
     • $Q$: finite set of states
     • $\Sigma$: finite set of input symbols
     • $O$: finite set of output symbols
     • $\delta: Q \times \Sigma \to Q$: transition function
     • $\lambda_{Mealy}: Q \times \Sigma \to O$: output function (maps state-input pairs to output symbols)
     • $q_0 \in Q$: initial state
   • A Mealy machine does not produce an initial output; it only outputs when an input is processed.

Justification: Construction of an Equivalent Mealy Machine from a Moore Machine

Let $M_{Moore} = (Q, \Sigma, O, \delta, \lambda_{Moore}, q_0)$ be an arbitrary Moore machine. We can construct an equivalent Mealy machine $M_{Mealy} = (Q', \Sigma, O, \delta', \lambda_{Mealy}, q'_0)$ as follows:

1. States: The set of states in the Mealy machine ($Q'$) will be the same as the set of states in the Moore machine ($Q$). So, $Q' = Q$.
2. Initial State: The initial state ($q'_0$) remains the same as $q_0$. So, $q'_0 = q_0$.
3. Transition Function: The transition function ($\delta'$) remains the same as $\delta$. So, $\delta' = \delta$.
4. Output Function: This is the crucial part. In a Moore machine, output is based on the state it enters. In a Mealy machine, output is based on the transition. When the Moore machine is in state $q$ and receives input $a$, it transitions to state $\delta(q, a)$ and then outputs $\lambda_{Moore}(\delta(q, a))$. To make the Mealy machine equivalent, when it is in state $q$ and receives input $a$, it should output the same symbol that the Moore machine would output after making the transition. Therefore, the output function for the Mealy machine is defined as: $\lambda_{Mealy}(q, a) = \lambda_{Moore}(\delta(q, a)) \quad \text{for all } q \in Q, a \in \Sigma$

Equivalence Definition: The Mealy machine constructed this way is considered equivalent to the Moore machine if, for any input string $w$, the output string produced by the Mealy machine is identical to the output string produced by the Moore machine, excluding the first character (which is the initial output of the Moore machine).

Example

Let's consider a simple Moore machine that outputs 'A' if the count of '1's in the input is even, and 'B' if the count of '1's is odd.

Moore Machine $M_{Moore}$:

• States $Q = \{q_{even}, q_{odd}\}$
• Input $\Sigma = \{0, 1\}$
• Output $O = \{A, B\}$
• Initial state $q_{even}$ (representing an even count of '1's initially)
• Transition function $\delta$:
  • $\delta(q_{even}, 0) = q_{even}$
  • $\delta(q_{even}, 1) = q_{odd}$
  • $\delta(q_{odd}, 0) = q_{odd}$
  • $\delta(q_{odd}, 1) = q_{even}$
• Output function $\lambda_{Moore}$:
  • $\lambda_{Moore}(q_{even}) = A$
  • $\lambda_{Moore}(q_{odd}) = B$

State Diagram of $M_{Moore}$:

Trace for input "101":

1. Start in $q_{even}$. Initial output: $A$
2. Input '1': Transition $q_{even} \to q_{odd}$. Output $\lambda_{Moore}(q_{odd}) = B$
3. Input '0': Transition $q_{odd} \to q_{odd}$. Output $\lambda_{Moore}(q_{odd}) = B$
4. Input '1': Transition $q_{odd} \to q_{even}$. Output $\lambda_{Moore}(q_{even}) = A$ Total output for "101": $ABBA$

Constructing Equivalent Mealy Machine $M_{Mealy}$

Using the construction rules:

• $Q' = \{q_{even}, q_{odd}\}$
• $q'_0 = q_{even}$
• $\delta'$ is the same as $\delta$.
• $\lambda_{Mealy}(q, a) = \lambda_{Moore}(\delta(q, a))$:
  • $\lambda_{Mealy}(q_{even}, 0) = \lambda_{Moore}(\delta(q_{even}, 0)) = \lambda_{Moore}(q_{even}) = A$
  • $\lambda_{Mealy}(q_{even}, 1) = \lambda_{Moore}(\delta(q_{even}, 1)) = \lambda_{Moore}(q_{odd}) = B$
  • $\lambda_{Mealy}(q_{odd}, 0) = \lambda_{Moore}(\delta(q_{odd}, 0)) = \lambda_{Moore}(q_{odd}) = B$
  • $\lambda_{Mealy}(q_{odd}, 1) = \lambda_{Moore}(\delta(q_{odd}, 1)) = \lambda_{Moore}(q_{even}) = A$

State Diagram of $M_{Mealy}$:

Trace for input "101" on $M_{Mealy}$:

1. Start in $q_{even}$. No initial output.
2. Input '1': From $q_{even}$, on '1', transition to $q_{odd}$ and output $\lambda_{Mealy}(q_{even}, 1) = B$.
3. Input '0': From $q_{odd}$, on '0', transition to $q_{odd}$ and output $\lambda_{Mealy}(q_{odd}, 0) = B$.
4. Input '1': From $q_{odd}$, on '1', transition to $q_{even}$ and output $\lambda_{Mealy}(q_{odd}, 1) = A$. Total output for "101": $BBA$

Conclusion

Comparing the outputs:

• $M_{Moore}$ output for "101": $ABBA$
• $M_{Mealy}$ output for "101": $BBA$

As observed, the output of the Mealy machine ($BBA$) is exactly the output of the Moore machine ($ABBA$) with its initial output ($A$) removed. This demonstrates the equivalence between the two machines under the standard definition.

Therefore, for any given Moore machine, an equivalent Mealy machine can always be constructed using the described method.

---

Solution Details:

• Explanation of the solution: To convert a Moore machine $M_{Moore} = (Q, \Sigma, O, \delta, \lambda_{Moore}, q_0)$ to an equivalent Mealy machine $M_{Mealy} = (Q', \Sigma, O, \delta', \lambda_{Mealy}, q'_0)$:

  1. Keep the same set of states ($Q' = Q$) and initial state ($q'_0 = q_0$).
  2. Keep the same transition function ($\delta' = \delta$).
  3. Define the Mealy output function $\lambda_{Mealy}(q, a)$ as the Moore output of the state reached after the transition: $\lambda_{Mealy}(q, a) = \lambda_{Moore}(\delta(q, a))$. The Mealy machine's output sequence for an input string will be the Moore machine's output sequence with its initial output symbol removed.

• Answer: The justification is provided by the general construction method and the illustrative example.