textbook on State Machines?

Thread Starter

MichealY

Joined Apr 9, 2009
49
Hi,I'm trying to figure out what mealy machine and moore machines are on the mathematics aspect.But I could find enough materials on my textbook and neither does it give good reference on this topic.

So could you recommand some textbooks on State Machines.

PS:
What's a state machines?
Whether a state machine is a automata?

Thanks in Advance.
MichealY.
 

studiot

Joined Nov 9, 2007
4,998
A 'State Machine' is another name for a sequential logic circuit. Since the storage capacity of sequential circuits is not infinite the term 'finite State Machine' is also used.

The circuits referred to are flip flops, latches, bistables, and so on.
A technique for drawing out the function of the circuit and showing what happens at each state is called

'Algorithmic State Chart (ASM)'

This is in two parts, comprising a 'State diagram' which is useful to concentrate on the transitions and a traditional logic flowchart.

A detailed textbook is

Modern Digital Design

Richar S Sandige

published by McGraw-Hill.
 
Last edited:

Thread Starter

MichealY

Joined Apr 9, 2009
49
Thanks for your reply.

Since I'm attempt to analysis these machines on mathematical aspect,we should concentrated on something mathematical.However,I think circuit belongs to area of electrical engineering.

Thanks to wikipedia at http://en.wikipedia.org/wiki/State_machine,
it seems state machine is much related to automata theory.

I'm lucky to have one book on this topic.It is Introduction to Automata Theory,Languages,and Computation by John E.Hopcroft,Rajjev Motwani,Jeffrey D.Ullman.

MichealY.
 

studiot

Joined Nov 9, 2007
4,998
Sandige seems pretty mathematical to me.

Perhaps you mean Turing Machines?

Computability and Logic
by G.S Boolos
& R.C. Jeffery

published by the Cambridge University Press

is a standard text.
 

RolfRomeo

Joined Apr 27, 2009
19
As far as I can recall the difference between a Moore and a Mealy machine is that the output of a Moore machine is solely dependent on the current state, whereas the output of a Mealy machine is also dependent on the current input. This typically means that a Mealy machine has some combinatorial logic between the sequential part and the output involving signals from the input side.
The two types of machines can be shown to be equivalent, and any machine of one type can be transformed into the other. Since you were interested in the mathematical side of things, I'm guessing this property is of interest to you.

Wikipedia has some info on the subject, and I'm sure some Google-digging will turn up a formal proof, if that's your fancy.

edit:

Also, I don't know of any particular book to recommend you (As I'm not sure excactly what you're after, and my total knowledge on the subject is summed up above), but I'd definitively try to find out whether Springer Books has anything on the subject. When it comes to dry condensed technical learning I find them hard to beat. And of course try and look up some academic articles if you have access to such a database.

founds a link: http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Seq/fsm.html This touches lightly on the subject, but includes most of the basics.
 
Last edited:

studiot

Joined Nov 9, 2007
4,998
As far as I can recall the difference between a Moore and a Mealy machine is that the output of a Moore machine is solely dependent on the current state, whereas the output of a Mealy machine is also dependent on the current input.
That would be correct

Further Moore, Mealy and Mixed type machines are Synchronous State Machines.

There's nearly a hundred pages about them in my first reference.

Mathematically the subject goes back to Turing and the Turing Machine, which, as the universal machine, is top of the heirarchy of types and from which the subsequent maths has flown.
 

Thread Starter

MichealY

Joined Apr 9, 2009
49
Mathematically the subject goes back to Turing and the Turing Machine, which, as the universal machine, is top of the heirarchy of types and from which the subsequent maths has flown.
Yes.I think mathematics on this subject should go back to Turing Machine,since both Mealy and Moore is transducers,transducers is finite state machine which is another name for finite state automata.Automata theory goes back to Turing Machine.

The book I referenced above is a classic in the automata theory,and some discrete course should teach something related to automata,lingustic,etc...

MichealY.
 
Top