number of states in Moore machine

[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

 

[Mike Treseler]

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

 

[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

 

[Ralf Hildebrandt]

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)

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

 

[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.

 

[Mike Treseler]

When you say comparing I
think you mean you will define a vector (as constant) and comparing
each input to arrary[index]. Right?

I would compare the constant to the shifter value on every clock.
Something like this:

http://home.comcast.net/~mike_treseler/shifter_sll.vhd
http://home.comcast.net/~mike_treseler/shifter_sll.pdf

-- Mike Treseler

 

[Symon]

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

Perhaps not...
http://en.wikipedia.org/wiki/Stephen_Wolfram#Discovery_of_the_simplest_universal_Turing_machine

Cheers, Syms.