The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
The number of states in 2’s complements Moore machine is ?

a. 2

b. 3

c. 4

d. 1
asked in Theory of Computation by Junior (519 points) | 1.2k views
I guess 3
Please explain how

1 Answer

0 votes
Best answer

I made this Moore State diagram for better understanding! Hope that helps!

answered by Active (1.5k points)
selected by

@Namit Dhupar how will you deal with the extra number generated by moore machine which is the start symbol in A


If I understand your question right @Red_devil, the question here is asking for 2's complement of any binary number...
Well, to do that, I learnt a little trick from somewhere, where given a binary number instead of finding a 1's complement and adding a 1 to LSB and then find the answer, what I do is-
1.) Take the given binary number and look at It's LSB
2.) while going from LSB to MSB all the 0's on the LSB as well as the last 1 from the LSB must be kept as it is and rest of the remaining digits should be complemented...

Here, let me show an example 
say  given binary is 11100  ---->  So 2' compliment will be (00100)  Highlighted digits are unchanged and rest complemented.
or 1111 -----> 0001 (Even if there are no 0's the 1 at the LSB should remain as it is and rest 1's complemented)

And no matter what and how long number you throw at it, this machine will accept it!


@  Namit Dhupar thanks for replying but my question is that when you are start in  state you are already generating 0 in your moore machine so your number will have an extra 0 in LSB , please correct me if i am wrong,

Oh, I forgot to mention, You have to feed the given binary number from LSB into the automata.

@Namit Dhupar  i am just asking what will  your machine generate if  no string is supplied to it.. i.e. epsilon.

Output of the initial state,0

Namit Dhupar yes!! that is what i am asking.. so every thing you generate will have a 0 at LSB how will you overcome this problem please explain.

I gotta be honest buddy, what I did was I originally derived the question in it's Mealy form and then converted it to Moore.
And the asker asked about the number of states which I immediately responded to, though you are right about Prefixes being always printed....
Can I have an (A,$\epsilon$) in the initial state with no transitions and make another state with say (X,0) with 0 as output, and then continue with rest of the automata, but this would make number of states as 4!
and general rule says, for K states in Mealy, there are K+1 states in Moore...
Other than that,What approach do you have in mind?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,259 questions
51,483 answers
66,769 users