Finites State Machine (OT?)

[Peter \"Firefly\" Lund]

On Fri, 14 May 2004, Andreas Hadler wrote:

How comes that I do your homework?

Because you couldn't stick to a single "no", the way I did?

In comp.arch we don't do people's home work. If we answer at all we give
correct but useless and misleading (but funny - to us) answers.

-Peter

 

[Tom Del Rosso]

In news:2gi0toF30judU1@uni-berlin.de,
pdx typed:

"The machine will accept the coins and eject a drinks can down the
vending chute when the correct money is inserted and the machine is
not empty." "The machine will reject the coins if the money is
incorrect for any reason - wrong amount or foreign coins etc. - or if
the machine is empty when the coins are inserted."

In response to your original question, it sounds like a job for a state
machine because it is sequential.

If you can, get a copy of "The Art of Digital Design" by Prosser and
Winkel. It has lots of examples with solutions to make it all clear,
and it uses a different notation that is much better than most books.

Also provided are the outputs: KeepCoins, EjectCoins, EmptySignOn,
EjectDrink.
and the inputs: MachineEmpty, AcceptCoins, RejectCoins

For example - does that mean "AcceptCoins" would be a state? Or would
the state be "Check coins", with "AcceptCoins" being an event?

"AcceptCoins" would be an input. "Event" is not a specific term in this
area. An input is not the same as a state. An input will help decide
what the "next state" is going to be.

Also, why would the examiner provide AcceptCoins *and* RejectCoins
since they should effectively always be the opposite of each other?

They are only sometimes "opposite" because only one can be true at a
time, and they can't both be true at the same time. But they are not
exactly opposite, because there are times when neither is true. That's
why they must be 2 separate signals.

What will the coin examiner mechanism do when it is still waiting for
coins? If it had only one output for accept/reject then that output
would have to show one or the other even when it doesn't know yet,
because it is still waiting for the coins.

The state machine needs 2 separate inputs so it can wait until 1 of them
becomes true.


--
-Reply in group, but if emailing add 2 more zeros-
-and remove the obvious-

 

[Greg Lindahl]

In article <40a3edb0$0$170$c3e8da3@news.astraweb.com>,
Frank Bemelman <f.bemelmanx@planet.invalid.nl> wrote:

A microprocessor *is* a finite state machine, no matter what software
you load it with.

You must be a mathematician. Consider programs like CRASHME...

-- greg

 

[Rich Grise]

"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...

Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of implementing
the control logic of a drinks vending machine?

Why is everyone answering this guy's exam question? If he doesn't understand
the subject matter well enough to take the test on his own, then he needs to
repeat the course, or go into banking.

Cheers!
Rich


(and of course, the definitive answer is, "Why not?")

;-)

 

[Rich Grise]

"pdx" <pdx@spamtrap.com> wrote in message
news:2gi176F36s3oU1@uni-berlin.de...

"Greg Lindahl" <lindahl@pbm.com> wrote in message
news:40a3ce15$1@news.meer.net...
In article <2ghvjqF3429bU1@uni-berlin.de>, pdx <pdx@spamtrap.com> wrote:

Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of
implementing
the control logic of a drinks vending machine?

Please send us the address of your professor. We'll send him the
answers directly, cutting out the middleman.

... or maybe one of you could go into the exam I'm sitting tomorrow?

I'll give you my student card and you've got approximately 14 hours to get
over here and learn my signature.


Certainly! My fee is $1000.00 per hour, portal to portal, all expenses

paid.

Eagerly anticipating the FedEx guy with my certified check,
Rich

 

[R. Steve Walz]

pdx wrote:

"Greg Lindahl" <lindahl@pbm.com> wrote:

Please send us the address of your professor. We'll send him the
answers directly, cutting out the middleman.

... or maybe one of you could go into the exam I'm sitting tomorrow?
----------------

If you didn't bother to read the chapter, why did you even bother
to go to school? Why don't you go bag groceries?

-Steve
--
-Steve Walz rstevew@armory.com ftp://ftp.armory.com/pub/user/rstevew
Electronics Site!! 1000's of Files and Dirs!! With Schematics Galore!!
http://www.armory.com/~rstevew or http://www.armory.com/~rstevew/Public

 

[R. Steve Walz]

Del Cecchi wrote:

"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...
Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of implementing
the control logic of a drinks vending machine?


Another trick question. These days it isn't an appropriate way. The
appropriate way is with an embedded microprocessor. Finite state machines
only made sense when microprocessors were too expensive.
------------

You're not grasping that state machines are also implemented with
microprocessors these days, it's not either-or.

-Steve
--
-Steve Walz rstevew@armory.com ftp://ftp.armory.com/pub/user/rstevew
Electronics Site!! 1000's of Files and Dirs!! With Schematics Galore!!
http://www.armory.com/~rstevew or http://www.armory.com/~rstevew/Public

 

[pdx]

"R. Steve Walz" <rstevew@armory.com> wrote in message
news:40A45755.3016@armory.com...

pdx wrote:

"Greg Lindahl" <lindahl@pbm.com> wrote:

Please send us the address of your professor. We'll send him the
answers directly, cutting out the middleman.

... or maybe one of you could go into the exam I'm sitting tomorrow?
----------------
If you didn't bother to read the chapter, why did you even bother
to go to school? Why don't you go bag groceries?

What are you talking about?

 

[pdx]

"Rich Grise" <null@example.net> wrote in message
news:i3Xoc.71162$sK3.49032@nwrddc03.gnilink.net...

"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...
Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of
implementing
the control logic of a drinks vending machine?



Why is everyone answering this guy's exam question?

It a question from a *past* exam.

If he doesn't understand
the subject matter well enough to take the test on his own, then he needs
to
repeat the course, or go into banking.

Ever thought that maybe this is a good way to help me understand the subject
matter?

If you don't like it don't reply. Your input isn't appreciated.

 

[Ketil Malde]

"Peter \"Firefly\" Lund" <firefly@diku.dk> writes:

On Thu, 13 May 2004, pdx wrote:

Also, why would the examiner provide AcceptCoins *and* RejectCoins since
they should effectively always be the opposite of each other?

No.

Zero points for this solution, but you earn ten bonus points for
attempting it in Prolog.

-kzm
--
If I haven't seen further, it is by standing in the footprints of giants

 

[Ketil Malde]

Steve <steve@thetaylorfamily.org.uk> writes:

Frank Bemelman wrote:

A microprocessor *is* a finite state machine, no matter what software
you load it with.

Alan Turing, "On Computable Numbers with an application to the
Entscheidungsproblem," 1936 ?

Let me try: A microprossessor with n bits of memory (including the
state of the microprossor) is a finite state machine with 2^n states.
Does that work?

-kzm
--
If I haven't seen further, it is by standing in the footprints of giants

 

[Fred Bloggs]

pdx wrote:

Why would a finite state machine be an appropriate method of implementing
the control logic of a drinks vending machine?

The answer is that the desired vending machine operation can be
configured into a finite sequence of events each of which is conditioned
on a well-defined state of partial completion of operation and inputs
that assume exactly one of two values such as YES/NO, TRUE/FALSE, GO/NOGO.

 

[Bernd Paysan]

Frank Bemelman wrote:

About KeepCoins and that diverter... to where does it divert? To the
internal
cashbox? And that Ejectcoins diverter dumps collected coins to the reject
bin, where the customer can take it out again? Again, I need to see the
machine. And that would be my answer during an exam too

There's probably a diverter that has to be closed to get acceptable coins
into the internal cashbox (which usually is a staple of coins). The
internal cashbox also must allow to emit coins (one by one) on the lower
side. If you don't want to have these parts time-critical, you need some
lock-stepping. E.g. if you insert a coin, the coin falls on the scales
(let's assume we just need to weight the coin). This must close the slot to
insert a new coin. If the coin is rejected, the scales open up to the
reject bin, otherwise the scales open up to the internal cashbox. If the
coin slides through either way, the slot is reopened. The internal cashbox
needs a slider which moves out one coin at a time to the reject bin if
necessary.

So "coin inserted" is an event, as is "coin accepted" or "coin rejected";
these events also drive the lock-stepping. "coin acceptable" is a flag
(generated by the scales after a suitable amount of time), but you also
could generate an event out of that flag (then you have two events: coin
acceptable/not acceptable). Outputs are pulses with specified duration (to
drive the mechanics). The machine needs internal bookkeeping (because when
you insert coins, you get an unbalanced account). There are at least three
accounts: money the machine owns, money inside the machine, but owned by
the customer, and things for sale (soft drink cans, or whatever) inside the
machine.

Does the machine need states in the classical sense? It has to react on
events (coin inserted, button pressed), and the actions in between
certainly can go through states. The states are not necessarily encoded in
the software. E.g. you are able to track where a coin is by looking at the
events, and you can create appropriate responses:

switch(wait_for_next_event()) {
coin_inserted: lock_slot(); break;
coin_acceptable: coin_value = scale_value(); coin_to_cashbox(); break;
coin_unacceptable: coin_to_rejectbin(); break;
coin_accepted: customer_balance += coin_value;
display_balance(customer_balance);
coin_rejected: unlock_slot(); break;
button_pressed: if((customer_balance > coke_price)
&& numbers_of_cokes[button]
&& eject_bin_is_empty())) {
eject_coke(button);
coke_price = price_table[button]; // more than one soft drink possible
customer_balance -= coke_price;
display_balance(customer_balance);
internal_balance += coke_price;
number_of_cokes[button]--;
if(numbers_of_cokes[button] < low_thres)
call_for("refill");
} break;
change_pressed: while(customer_balance > 0) {
coin_value = eject_largest_coin(customer_balance);
if(coin_value == 0) call_for("coins");
customer_balance -= coin_value;
display_balance(customer_balance);
} break;
timeout: call_for("service"); break;
}

Where are the states? You have some variables like slot locked/unlocked,
which are mechanical states. It makes sure that you go from state coin
insert to coin check and coin accept/reject in a sequence, without
disturbance. Generally, however, every "state" is reachable anytime. E.g.
if you want to get out 20 cans of coke out of this machine, you can have
one person inserting quarters as fast as possible (20 cokes at 60˘, that's
48 quarters), and another person could press the "coke" button as fast as
the machine delivers (which is probably slower) without taking care of the
precise order of events.

If you have a classical state machine, getting 20 cokes for 60˘ is more
time-consuming. You need two quarters and a dime for each coke (or six
dimes or two quarters and two nickles...) or three quarters and get a dime
and a nickel in return. For each coke, you must fill the machine with the
appropriate amount of money, and *then* press the button. You'll get the
coke and the return (both takes time). Only now the machine is ready to
accept coins again. You are forced to reuse the return money.

State machines vs. event driven machines are a typical case of unnecessary
sequentializing. Enforce sequential parts through locks, not through
states. It's even not sure if you need the coin lock. Maybe it's
mechanically impossible to enter more coins than the scales can measure in
that time. Or the failure mode for two coins on the scales at the same time
is that they get rejected, anyway.

--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/

 

[Marlboro]

"pdx" <pdx@spamtrap.com> wrote in message news:<2gi0toF30judU1@uni-berlin.de>...

"Rene Tschaggelar" <none@none.net> wrote in message
news:40a3cb19$0$705$5402220f@news.sunrise.ch...
pdx wrote:

Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of
implementing
the control logic of a drinks vending machine?

A state machine is a model consisting of a number of states
where events cause actions that can change the state. It can model
almost anything.

Subdivide the problem into static states and define the event that cause
actions.

"The machine will accept the coins and eject a drinks can down the vending
chute when the correct money is inserted and the machine is not empty."
"The machine will reject the coins if the money is incorrect for any
reason - wrong amount or foreign coins etc. - or if the machine is empty
when the coins are inserted."

Also provided are the outputs: KeepCoins, EjectCoins, EmptySignOn,
EjectDrink.
and the inputs: MachineEmpty, AcceptCoins, RejectCoins

For example - does that mean "AcceptCoins" would be a state? Or would the
state be "Check coins", with "AcceptCoins" being an event?

Also, why would the examiner provide AcceptCoins *and* RejectCoins since
they should effectively always be the opposite of each other?

Well, because there will be a situation when the machine will
AcceptCoins and do nothing. I call that a Robber state machine.

 

[Sander Vesik]

In comp.arch R. Steve Walz <rstevew@armory.com> wrote:

Del Cecchi wrote:

"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...
Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of implementing
the control logic of a drinks vending machine?


Another trick question. These days it isn't an appropriate way. The
appropriate way is with an embedded microprocessor. Finite state machines
only made sense when microprocessors were too expensive.
------------
You're not grasping that state machines are also implemented with
microprocessors these days, it's not either-or.

You should read up on Del's posting history. He grasps a rather disconcerningly
large amount of very complex things.

-Steve

--
Sander

+++ Out of cheese error +++

 

[Active8]

On Fri, 14 May 2004 12:54:35 GMT, Fred Bloggs wrote:

pdx wrote:

Why would a finite state machine be an appropriate method of implementing
the control logic of a drinks vending machine?


The answer is that the desired vending machine operation can be
configured into a finite sequence of events each of which is conditioned
on a well-defined state of partial completion of operation and inputs
that assume exactly one of two values such as YES/NO, TRUE/FALSE, GO/NOGO.

Wow! Well put. I'm glad I skipped to your post. Everyone else was
blathering on without answering the question.

I might add for future reference that the finite state machine can
be visualized with the aid of a state diagram which will aid in
defining the logic to be implemented.

--
Best Regards,
Mike

 

[Soeren]

Hi Ketil,

No.

Zero points for this solution, but you earn ten bonus points for
attempting it in Prolog.

Goal-seeking for a "No" ? That would be easy points earned


--
Regards,
Soeren

* If it puzzles you dear... Reverse engineer *

 

[R. Steve Walz]

Sander Vesik wrote:

In comp.arch R. Steve Walz <rstevew@armory.com> wrote:
Del Cecchi wrote:

"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...
Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of implementing
the control logic of a drinks vending machine?


Another trick question. These days it isn't an appropriate way. The
appropriate way is with an embedded microprocessor. Finite state machines
only made sense when microprocessors were too expensive.
------------
You're not grasping that state machines are also implemented with
microprocessors these days, it's not either-or.

You should read up on Del's posting history. He grasps a rather disconcerningly
-----------------

And so you're his doting fellatrix?

large amount of very complex things.
-------------------

So may he. So do I.
But which may still exclude the truth I mentioned on his part.

You see:
I don't HAVE to know everything to be smarter than YOU are.
Grasp set theory, over and against statistics you can't know.

-Steve
--
Sander
+++ Out of cheese error +++
--------------------

Get some Wensleydale!

-Steve
--
-Steve Walz rstevew@armory.com ftp://ftp.armory.com/pub/user/rstevew
Electronics Site!! 1000's of Files and Dirs!! With Schematics Galore!!
http://www.armory.com/~rstevew or http://www.armory.com/~rstevew/Public

 

[del cecchi]

"R. Steve Walz" <rstevew@armory.com> wrote in message
news:40A560A6.5C9F@armory.com...

Sander Vesik wrote:

In comp.arch R. Steve Walz <rstevew@armory.com> wrote:
Del Cecchi wrote:

"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...
Sorry if this is off topic but I have another question to help
with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of
implementing
the control logic of a drinks vending machine?


Another trick question. These days it isn't an appropriate way.
The
appropriate way is with an embedded microprocessor. Finite
state machines
only made sense when microprocessors were too expensive.
------------
You're not grasping that state machines are also implemented with
microprocessors these days, it's not either-or.

You should read up on Del's posting history. He grasps a rather
disconcerningly
-----------------
And so you're his doting fellatrix?


large amount of very complex things.
-------------------
So may he. So do I.
But which may still exclude the truth I mentioned on his part.

You see:
I don't HAVE to know everything to be smarter than YOU are.
Grasp set theory, over and against statistics you can't know.


Well, schematics galore. Wasn't your sister in a james bond movie?

I should have trimmed followups. comp.arch has a tradition of spoofing
folks looking for help with homework or evidencing lazyness and
cluelessness. I guess you whiz bang circuit designers over in the other
groups didn't catch on, and have nothing better to do than be volunteer
tutors.

Thanks for letting me know that one can implement state machines in
microcode. It had never occurred to me.
I shall be more careful in my followups in the future so as not to mess
your sandbox.

del cecchi

 

[Terry Given]

"pdx" <pdx@spamtrap.com> wrote in message
news:2ghvjqF3429bU1@uni-berlin.de...

Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of implementing
the control logic of a drinks vending machine?

The answer to your question is simple - because it can be made to work.

IME, programmers who dont understand state machines are talentless fools,
who tend to write lousy code. Alas, they can usually draw pretty GUIs so
people keep hiring them *sigh*

Terry