5 ms·

And "Decision Tables" often lead one into the wonderful world of Finite State Machines[0], another fundamental concept "rarely taught/known nowadays." The appl

And "Decision Tables" often lead one into the wonderful world of Finite State Machines[0], another fundamental concept "rarely taught/known nowadays." The applicability of both in many problem domains remains a source of pleasant surprise to me to this day. 0 - https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Finite-state_machine

082349872349872 3y ago
As a non-CS major who had encountered finite state machines in my early teens, it boggles my mind to consider that nowadays someone could successfully get through a CS curriculum without them. (a trie ain't nothing but a degenerate state machine) On second thought, this is a wonderful hypothesis, because it would explain so much about the modern software environment...
- 3abiton 3y ago
  What makes them essential? Never have I encountered them
  - zby 3y ago
    They are the Turing Machine without the (infinite) tape. What is your favourite abstraction of computer?
    - egormakarov 3y ago
      About 100kb of carefully crafted yaml configs
  - thebruce87m 3y ago
    They are used extensively in embedded software. A device will be in one of several states - running, sleep, configuration, log download and so on. Each state is a C function (for me). I normally have entry/exit functions for each state too so that you set up/tear down the hardware needed for each. As you add more states, you do not need to edit the existing states - well only the bits where you need to transition to the new state. This makes it much easier to maintain and reason about. Each subsystem can be its own state machine too.
  - 082349872349872 3y ago
    You've certainly used them, but been unaware of it. Made a menu selection? State Machine. Interacted with a dialogue box/an HTML form? State Machine. Used a dropdown/popup suggestions list? State Machine. Written async code? State Machine. Used a VM? State Machine. Used a compiled executable? State Machine. Any time you don't have all the input available when you start (equivalently, can be interrupted by some other task) either you explicitly, or a tool on your behalf implicitly, will need to reach for a state machine. Even if all the input is in principle available, if it is too large for practical processing, piece-by-piece processing entails a state machine (however rudimentary). https://lamport.azurewebsites.net/pubs/state-machine.pdf https://lamport.azurewebsites.net/pubs/state-machine.pdf "safety" (nothing bad ever happens) and "liveness" (something good eventually happens) are two key properties for systems, and they both have easy formalisations in state machine terms.
  - AdieuToLogic 3y ago
    As others have pointed out, FSM's are very useful to formalize/organize behaviour in a stateful workflow. One domain where I think they shine is in implementing structured binary format decoders (such as multimedia streams). Here is a brief introduction which may be of help: https://www.cs.princeton.edu/courses/archive/spr06/cos116/FSM_Tutorial.pdf https://www.cs.princeton.edu/courses/archive/spr06/cos116/FS...
  - rramadass 3y ago
    As the other responder points out you use state machines everyday without knowing it. A "State Machine" is a mathematical abstraction (i.e. a "computation" model) for the workings of a concrete machine i.e. A real Computer running a Program. When you start to write your programs as state machines you make its operations explicit, unambiguous and clear thus greatly reducing errors and guaranteeing "correctness". This is what makes it "essential". I highly recommend studying Michael Sipser's Introduction to the Theory of Computation to understand this and other computation models (any edition will do).

082349872349872 3y ago

As a non-CS major who had encountered finite state machines in my early teens, it boggles my mind to consider that nowadays someone could successfully get through a CS curriculum without them. (a trie ain't nothing but a degenerate state machine) On second thought, this is a wonderful hypothesis, because it would explain so much about the modern software environment...

3abiton 3y ago
What makes them essential? Never have I encountered them
- zby 3y ago
  They are the Turing Machine without the (infinite) tape. What is your favourite abstraction of computer?
  - egormakarov 3y ago
    About 100kb of carefully crafted yaml configs
- thebruce87m 3y ago
  They are used extensively in embedded software. A device will be in one of several states - running, sleep, configuration, log download and so on. Each state is a C function (for me). I normally have entry/exit functions for each state too so that you set up/tear down the hardware needed for each. As you add more states, you do not need to edit the existing states - well only the bits where you need to transition to the new state. This makes it much easier to maintain and reason about. Each subsystem can be its own state machine too.
- 082349872349872 3y ago
  You've certainly used them, but been unaware of it. Made a menu selection? State Machine. Interacted with a dialogue box/an HTML form? State Machine. Used a dropdown/popup suggestions list? State Machine. Written async code? State Machine. Used a VM? State Machine. Used a compiled executable? State Machine. Any time you don't have all the input available when you start (equivalently, can be interrupted by some other task) either you explicitly, or a tool on your behalf implicitly, will need to reach for a state machine. Even if all the input is in principle available, if it is too large for practical processing, piece-by-piece processing entails a state machine (however rudimentary). https://lamport.azurewebsites.net/pubs/state-machine.pdf https://lamport.azurewebsites.net/pubs/state-machine.pdf "safety" (nothing bad ever happens) and "liveness" (something good eventually happens) are two key properties for systems, and they both have easy formalisations in state machine terms.
- AdieuToLogic 3y ago
  As others have pointed out, FSM's are very useful to formalize/organize behaviour in a stateful workflow. One domain where I think they shine is in implementing structured binary format decoders (such as multimedia streams). Here is a brief introduction which may be of help: https://www.cs.princeton.edu/courses/archive/spr06/cos116/FSM_Tutorial.pdf https://www.cs.princeton.edu/courses/archive/spr06/cos116/FS...
- rramadass 3y ago
  As the other responder points out you use state machines everyday without knowing it. A "State Machine" is a mathematical abstraction (i.e. a "computation" model) for the workings of a concrete machine i.e. A real Computer running a Program. When you start to write your programs as state machines you make its operations explicit, unambiguous and clear thus greatly reducing errors and guaranteeing "correctness". This is what makes it "essential". I highly recommend studying Michael Sipser's Introduction to the Theory of Computation to understand this and other computation models (any edition will do).