(Maybe off topic) Can someone explain what a finite state machine is?

[Matty Sarro]

Hey everyone. I am currently reading through an RFC, and it mentions
that a client and server half of a transaction are embodied by finite
state machines. I am reading through the wikipedia article for finite
state machines, and sadly it's going a bit above my head. I don't
really have a background in engineering, and would really love to
understand what is being said. Does anyone have a simple way to
explain it?

 

[Michael Brown]

Hey everyone. I am currently reading through an RFC, and it mentions
that a client and server half of a transaction are embodied by finite
state machines. I am reading through the wikipedia article for finite
state machines, and sadly it's going a bit above my head. I don't
really have a background in engineering, and would really love to
understand what is being said. Does anyone have a simple way to
explain it?

We can mathematically model a finite state machine (FSM) by a simple
system characterized by three quantities:

* state
* input
* output

and two functions:

* next_state_function(current_state, current_input)
* output_function(current_state, current_input)

The quantities' values are only defined between transitions, as we accept
that their values change non-continuously at each transition "tick". Thus,
at each transition the following pseudocode is run:

state <- next_state_function(state, input)

And at any point in time, the output satisfies the equation:

output = output_function(state, input)

 

[Steven D'Aprano]

Hey everyone. I am currently reading through an RFC, and it mentions
that a client and server half of a transaction are embodied by finite
state machines. I am reading through the wikipedia article for finite
state machines, and sadly it's going a bit above my head. I don't
really have a background in engineering, and would really love to
understand what is being said. Does anyone have a simple way to
explain it?

Consider a heater with a thermostat. That's a finite state machine. It's a
machine, it has a finite number of states, namely, the combinations of
these:

"on" or "off"
"too warm", "too cold" or "in-between"

The machine has transitions between states:

"if too warm, then turn off"
"if too cold, then turn on"
"if in-between, then don't change"


Here's one way to simulate such a simple FSM in Python:


import time

class Heater:
low = 0
high = 10
def __init__(self, starting_temperature=7):
self.temp = starting_temperature
self.state = "off"
def run(self):
while True:
if self.state == "on":
# Heating.
self.temp += 1
if self.state == "off":
# Slowly cooling.
self.temp -= 1
if self.temp < self.low:
print("turning on")
self.state = "on"
if self.temp > self.high:
print("turning off")
self.state = "off"
time.sleep(1)


turning on
turning off
turning on
turning off
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 9, in run
KeyboardInterrupt



More complex finite state machines can have many different states, and much
more complicated behaviour.

 

[rusi]

Hey everyone. I am currently reading through an RFC, and it mentions
that a client and server half of a transaction are embodied by finite
state machines. I am reading through the wikipedia article for finite
state machines, and sadly it's going a bit above my head. I don't
really have a background in engineering, and would really love to
understand what is being said. Does anyone have a simple way to
explain it?

Yes... "background in engineering" is what a layperson would assume
from the words "finite state machine" but this is not really so
(unless you think math is the same as engineering) because the words
were invented by mathematicians (no normal engineer would call a
machine an 'automaton' -- the original name!)

So assuming and staying within python a natural example would be what
is called lexical analysis or tokenizing.

Say you have a line of python like:

def foo(count, x ="if nothing is given") # catch a comment anyone?

the python interpreter in its lexical analysis phase breaks this up as
|def|foo|(|count|,|x||=|"if nothing is given"|)|<Comment DISCARDED>

Some of the things it does are:
1. Separating between all these tokens or lexemes
2. Distinguishing identifiers like foo, count, x (there's no
difference at this stage) from keywords like def
3. Discarding spaces but after using them to separate 'def' from 'foo'
4. Identifying special symbols like ( , = etc
5. Throwing away the comment

Now how does python know that the catch in the comment (or the if in
the string) are not the python keywords?

Well this is where the notion of state comes in:
It starts in a default or normal state but when it sees the " it goes
to (or is it gotos?) a state which we may call InsideStringState. In
this state everything is swallowed up indiscriminately until the next
" Likewise an InCommentState would swallow up everything from # to
newline.

So to tokenize python it would be natural to think with 3 states:
Normal, InString and InComment

Of course in real programming languages there would be many more
states than 3.
eg What happens when the machine is in InString state and you
encounter a backslash?

Or more hairy example: Say you have a language like C whose comments
are /*... */
Now when you see a / is it a divide symbol or a comment?
All such problems get solved by introducing suitable states like
MaybeComment


In short, dont focus your attention on 'machine' but on 'state' and
you should be fine