5 ms·

What are the typical (or potential) use cases for FSMs? I do web development. Is it something that could help me better model rules for a business domain, for

What are the typical (or potential) use cases for FSMs? I do web development. Is it something that could help me better model rules for a business domain, for example?

unhammer 11y ago
They are heavily used in natural language processing, e.g. for modeling dictionaries (using finite state transducers, where the input side has the inflected form, output side has the dictionary form+part of speech), part of speech taggers (markov chains can be implemented by finite state machines). Note also that regular expressions (the kind you find in sed/awk, not the perl extended stuff) are equivalent in power to finite state machines – a regex can be modelled by an FSM, and an FSM can be turned into a regex. Outside of NLP, they can be used anywhere you can implement your logic as a transition table with rows like "fromstate,input,tostate,action". I believe it's common for many servers and network stuff to do this. https://en.wikipedia.org/wiki/State_pattern https://en.wikipedia.org/wiki/State_pattern and https://en.wikipedia.org/wiki/Automata-based_programming#Example https://en.wikipedia.org/wiki/Automata-based_programming#Exa... have some fairly traditional examples. One of the plus-sides of finite state machines is that they are formally less powerful than full turing machines. This might make it easier to check that a program does what it should, but they also compose in ways that full turing machines (or intermediate-level machines like context-free or context-sensitive) can't. E.g. you can take two FSM's, and do a set intersection/union/difference/kleene star/concatenation/reverse and still stay within finite state (unlike e.g. context free, where you can't do intersection/difference). But it also means there are certain types of logic you can't express within finite state.
- burntsushi 11y ago
  To add another one: Lucene uses a finite state transducer to represent a part of its term index: http://blog.mikemccandless.com/2010/12/using-finite-state-transducers-in.html http://blog.mikemccandless.com/2010/12/using-finite-state-tr... --- It's essentially a dictionary as you say, but instead of a direct NLP use case, it might map a word to some numerical value (like a file offset where the term's postings list resides). I actually haven't been able to find anyone else using transducers for this purpose (sans OpenSextant, I think), but I'd be curious to hear about it if others knew. It seems like a really awesome way to represent nearly arbitrary maps/sets of billions of strings.
- emmelaich 11y ago
  The Augeas project has a finite automaton at it's heart: https://github.com/hercules-team/augeas/blob/master/src/fa.c https://github.com/hercules-team/augeas/blob/master/src/fa.c
danielvf 11y ago
I've coded some systems which use tons of force to move pieces of metal through the same space that moments earlier were occupied by humans or human limbs. This was Scary. I turned to state machines. In ten years, neither of these two systems I coded has had a single software bug - not even in testing. Imagine you have a emergency stop button (or two) on a machine. What needs to happen when that button is pressed? The machine needs to stop of course - but "stop" means radically different things depending on what the machine is doing at the time. If, say, a part is clamped in the machine, and a couple tons of cutting force is being applied to that part, an emergency stop had better keep that part held in place, or chunks metal will be exploding everywhere. On the other hand, if the clamping process has just started, the machine needs to stop applying pressure on the clamp. When you figure that even a simple machine might have 30 outputs that need to be controlled, and 30 inputs coming in, trying to solve this kind of problem with if statements guarantees that you will miss something. And you will be unable to reason about it later. With state machines however, you can make provably correct software. For every state in the system, I can see exactly what the machine should be doing in that state, and every possible transition out of that state. Alternately, I can take a given input or output, and see every possible effect it will have on the system. For example, I can review every state to see what happens when the emergency stop is pressed, and make sure that it does the right thing. Or I can work through the flow of states. In the "Clamping" state an emergency stop will cause a transition to the "Estop Clamp Open State" which release pressure to the clamp and turns off lots of spinning bits on the machine. Afterwords, when emergency stop is released, the machine transitions to the "Reset, Clamp Open" state which starts the process of moving things around to get back to normal. Once every sensor reports that everything has been reset, the machine transitions back to "Ready", and we are ready for the next transition. For web applications, I use state machines for business process logic. Usually this can be a lot less formal - just a state field in table, with methods that check that field to decide how to act, what is allowed, or to transition states.
harlowja 11y ago
A few openstack projects also use them, to explicitly define the transitions there resources (and/or other objects) will go through in a controlled manner. http://docs.openstack.org/developer/ironic/dev/states.html http://docs.openstack.org/developer/ironic/dev/states.html https://github.com/openstack/automaton https://github.com/openstack/automaton http://docs.openstack.org/developer/taskflow/states.html http://docs.openstack.org/developer/taskflow/states.html

What are the typical (or potential) use cases for FSMs? I do web development. Is it something that could help me better model rules for a business domain, for example?

unhammer 11y ago

They are heavily used in natural language processing, e.g. for modeling dictionaries (using finite state transducers, where the input side has the inflected form, output side has the dictionary form+part of speech), part of speech taggers (markov chains can be implemented by finite state machines). Note also that regular expressions (the kind you find in sed/awk, not the perl extended stuff) are equivalent in power to finite state machines – a regex can be modelled by an FSM, and an FSM can be turned into a regex. Outside of NLP, they can be used anywhere you can implement your logic as a transition table with rows like "fromstate,input,tostate,action". I believe it's common for many servers and network stuff to do this. https://en.wikipedia.org/wiki/State_pattern https://en.wikipedia.org/wiki/State_pattern and https://en.wikipedia.org/wiki/Automata-based_programming#Example https://en.wikipedia.org/wiki/Automata-based_programming#Exa... have some fairly traditional examples. One of the plus-sides of finite state machines is that they are formally less powerful than full turing machines. This might make it easier to check that a program does what it should, but they also compose in ways that full turing machines (or intermediate-level machines like context-free or context-sensitive) can't. E.g. you can take two FSM's, and do a set intersection/union/difference/kleene star/concatenation/reverse and still stay within finite state (unlike e.g. context free, where you can't do intersection/difference). But it also means there are certain types of logic you can't express within finite state.

burntsushi 11y ago
To add another one: Lucene uses a finite state transducer to represent a part of its term index: http://blog.mikemccandless.com/2010/12/using-finite-state-transducers-in.html http://blog.mikemccandless.com/2010/12/using-finite-state-tr... --- It's essentially a dictionary as you say, but instead of a direct NLP use case, it might map a word to some numerical value (like a file offset where the term's postings list resides). I actually haven't been able to find anyone else using transducers for this purpose (sans OpenSextant, I think), but I'd be curious to hear about it if others knew. It seems like a really awesome way to represent nearly arbitrary maps/sets of billions of strings.
emmelaich 11y ago
The Augeas project has a finite automaton at it's heart: https://github.com/hercules-team/augeas/blob/master/src/fa.c https://github.com/hercules-team/augeas/blob/master/src/fa.c

danielvf 11y ago

I've coded some systems which use tons of force to move pieces of metal through the same space that moments earlier were occupied by humans or human limbs. This was Scary. I turned to state machines. In ten years, neither of these two systems I coded has had a single software bug - not even in testing. Imagine you have a emergency stop button (or two) on a machine. What needs to happen when that button is pressed? The machine needs to stop of course - but "stop" means radically different things depending on what the machine is doing at the time. If, say, a part is clamped in the machine, and a couple tons of cutting force is being applied to that part, an emergency stop had better keep that part held in place, or chunks metal will be exploding everywhere. On the other hand, if the clamping process has just started, the machine needs to stop applying pressure on the clamp. When you figure that even a simple machine might have 30 outputs that need to be controlled, and 30 inputs coming in, trying to solve this kind of problem with if statements guarantees that you will miss something. And you will be unable to reason about it later. With state machines however, you can make provably correct software. For every state in the system, I can see exactly what the machine should be doing in that state, and every possible transition out of that state. Alternately, I can take a given input or output, and see every possible effect it will have on the system. For example, I can review every state to see what happens when the emergency stop is pressed, and make sure that it does the right thing. Or I can work through the flow of states. In the "Clamping" state an emergency stop will cause a transition to the "Estop Clamp Open State" which release pressure to the clamp and turns off lots of spinning bits on the machine. Afterwords, when emergency stop is released, the machine transitions to the "Reset, Clamp Open" state which starts the process of moving things around to get back to normal. Once every sensor reports that everything has been reset, the machine transitions back to "Ready", and we are ready for the next transition. For web applications, I use state machines for business process logic. Usually this can be a lot less formal - just a state field in table, with methods that check that field to decide how to act, what is allowed, or to transition states.

harlowja 11y ago

A few openstack projects also use them, to explicitly define the transitions there resources (and/or other objects) will go through in a controlled manner. http://docs.openstack.org/developer/ironic/dev/states.html http://docs.openstack.org/developer/ironic/dev/states.html https://github.com/openstack/automaton https://github.com/openstack/automaton http://docs.openstack.org/developer/taskflow/states.html http://docs.openstack.org/developer/taskflow/states.html