edited by
4,292 views
6 votes
6 votes

Let $P$ be a Mealy machine that has $N$ states and $M$ outputs. Let $Z$ be the number of states of the corresponding Moore machine $Q$ which is equivalent to $P$. Which of the following conditions always holds?

  1. $Z<M+N$
  2. $Z=M*N$
  3. $Z=P*M+Q*N$
  4. $Z \leq M*N$
edited by

3 Answers

4 votes
4 votes
In Moore to Mealy conversion, the number of states are same.

In Mealy to Moore conversion, the number of states in worst case can be N*M.

i.e the number of states in Moore are equal or more than its equivalent Mealy machine.
2 votes
2 votes

In a Moore machine as we know each state has a fixed output. Hence suppose if we make a transition from one state whose output is 1 to another state, it will have a definite output defined for that state. In Mealy machine that is not the case the Automata accept an input symbol, generates an output symbol and if designed may or may not change states. Perhaps the diagram below will make it clear.

So for each state N in Mealy machine, we have Z number of states is Moore machine where Z=N*(number of output symbols). or Z=M*N

Z<N *(number of output symbol) or Z<N*M only when we define redundant states in Mealy Machine that is when further reduction is possible. Thus, a general answer $Z\leqslant M*N$

 

0 votes
0 votes
If a Mealy machine has "n" states and "m" output then corresponding Moore

    machine may have "m*n" states.

 

 

D is correct
Answer:

Related questions