Languages, Moore and Meally Machines

Moore and Meally Machines

A moore machine produces an output for each state. An fsm is thus a moore machine with two outputs, success and failure, corresponding to final and nonfinal states respectively.

A meally machine produces an output for each transition (state/input pair). A moore machine can be transformed into an equivalent mealy machine by associating the output of each state with every transition that leads to that state. The languages accepted are the same (although the mealy machine doesn't recognize E).

To transform a mealy machine into a more machine, create a state for each state/output pair. In this example there are two possible outputs, 0 and 1. If state q on A goes to r, producing 1 in the mealy machine, then q0 and q1 on A go to r1, and the state r1 produces the output 1. Verify that this moore machine produces the same output as the original meally machine, for any given input string.