GATE Overflow | Mock GATE | Test 1 | Question: 17

Question

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?

• A. $Z<M+N$
• B. $Z=M*N$
• C. $Z=P*M+Q*N$
• D. $Z \leq M*N$

Comments

if we convert melay to moore then no of state remain same or may increase so first 3 options are ruled out

---

@Nilabja Sarkar how can you elemenate first 3?

RHS is given as function of both states and output ,where as LHS is only states of MOORE machine

---

P->Melay m/c now corresponding  moore m/c means we are covering melay to moore . so the states will remain same otherwise increase let take a case of 2s complement no melay take 2 state   2 o/p moore take 3 state . its not perfect  proof i am thinking that way

Answer 1

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.

Comments

baburavula says

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

    machine may have "m*n" states.

Answer 2

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$

 

Answer 3

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

    machine may have "m*n" states.

 

 

D is correct