number of states in Moore machine

[Symon]

"Ralf Hildebrandt" <Ralf-Hildebrandt@gmx.de> wrote in message
news:5p6b48FpfcvjU1@mid.individual.net...

Brian Drummond schrieb:

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

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

Cheers, Syms.

 

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

Amit wrote:

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]

On Sun, 04 Nov 2007 01:37:03 -0800, Amit <amit.kohan@gmail.com> wrote:

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]

Brian Drummond schrieb:

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]

On Nov 4, 8:41 am, Ralf Hildebrandt <Ralf-Hildebra...@gmx.de> wrote:

Brian Drummond schrieb:

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

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]

Amit wrote:

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