number of states in Moore machine

A

Amit

Hi group,

I'm implementing a Moore machine which receives a string as
"000010000100".

Can I consider 12 states for this? or there is a better or more
optimized way? considering that in case of an invalid input the system
must gets reset or gets back to the first state.

Also, can we base on length of a string predict how many states we
would have?

thanks.
amit
 
M

Mike Treseler

Amit said:
I'm implementing a Moore machine which receives a string as
"000010000100".

I am sorry to hear that your instructor would
suggest such an unproductive design process.
Can I consider 12 states for this? or there is a better or more
optimized way? considering that in case of an invalid input the system
must gets reset or gets back to the first state.

I would declare a 12 bit vector variable,
and on each rising edge, shift in a bit
and compare the register value to "000010000100".
Also, can we base on length of a string predict how many states we
would have?

A state machine is the worst possible
description for a shift register and
such a prediction would not help solve
the problem in any case. I might add
a 4 bit counter register to delay detection
until at least 12 bits were shifted in
since reset.

-- Mike Treseler
 
B

Brian Drummond

Hi group,

I'm implementing a Moore machine which receives a string as
"000010000100".

Can I consider 12 states for this? or there is a better or more
optimized way? considering that in case of an invalid input the system
must gets reset or gets back to the first state.

Also, can we base on length of a string predict how many states we
would have?

thanks.
amit

It depends on what the machine is doing with the string.

Hint: you can build a finite state machine to process infinite strings,
if there are some restrictions on the processing required.

(I believe some guy wrote a paper about that in 1936)

- Brian
 
R

Ralf Hildebrandt

A

Amit

You are talking about Alan Turing?
<http://www.wolframscience.com/prizes/tm23/images/Turing.pdf>

Hint: Steven Wolframs smallest Turing machine has been proven to be
universal during the last weeks:
<http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf>

Ralf


Thanks to you all. also, I appreciate you for the PDF files you
shared. Mike, I have a question for you; When you say comparing I
think you mean you will define a vector (as constant) and comparing
each input to arrary[index]. Right?

Thanks.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top