3 ms·

They are not powerful enough to model complex UIs. In terms of expressiveness, state machines are equivalent to regular expressions. That's why I find the title

by dukoid 7y ago

They are not powerful enough to model complex UIs. In terms of expressiveness, state machines are equivalent to regular expressions. That's why I find the title quite misleading. They may be useful to some extent for very simple UIs (for instance, Siemens Mobile has used them to model mobile phone (app) UIs).

TFortunato 7y ago
Statecharts are not the same as simple Finite State Machines.
emmanueloga_ 7y ago
Statecharts _builds upon_ state machines, but is a more powerful language to model a system's state than FSMs or regular expressions. There's a good explanation here [1]. 1: https://stackoverflow.com/a/40679958/855105 https://stackoverflow.com/a/40679958/855105
- dukoid 7y ago
  What's their expressiveness? I always thought the nesting could be "flattened", so it wouldn't really make a difference?
  - emmanueloga_ 7y ago
    Flattening the nested states would produce an explosion of states. This page describes how Statecharts avoids that [1]. In regard to expressivity, specially compared with FSM, a thorough description can be find in the paper "On Visual Formalisms" [2]. I copy some points here for convenience: ...people working on the design of really complex systems have all but given up on the use of conventional FSMs and their state diagrams for several reasons (1) State diagrams are “flat.” They provide no natural notion of depth, hierarchy, or modularity + orthogonality + broadcast communication. (2) State diagrams are uneconomical when it comes to transitions [...] resulting in an unnecessary multitude of arrows. (3) State diagrams are [...] infeasible: as the system under description grows linearly, the number of states grows exponentially. (4) State diagrams are inherently sequential in nature and do not cater for concurrency in a natural way. 1: https://statecharts.github.io/state-machine-state-explosion.html https://statecharts.github.io/state-machine-state-explosion.... 2: http://www.dcs.ed.ac.uk/home/kxt/on_visual_formalisms.pdf http://www.dcs.ed.ac.uk/home/kxt/on_visual_formalisms.pdf
  - mcphage 7y ago
    State charts have parallel states, which require an exponential number of states with a finite state machine. And it supports history—returning to a container state can return to the last entered state in that container, whichever it was—I’m not sure if finite state machines can support that or not. Maybe they can, but again, it would vastly explode the state space.
deleted 7y ago
[deleted]
brucou 7y ago
State machines are a generic term. You will find here the different kinds of state machines, with varying expressive power that are used in computer science and actuak programming: https://github.com/achou11/state-machines https://github.com/achou11/state-machines In any case, keep in mind that Turing machines are (extended) state machines (albeit with infinite memory) so the expressive power of state machine is at least anything computable (sequentially - turing machine is a model of sequential computation).

by dukoid 7y ago

TFortunato 7y ago

Statecharts are not the same as simple Finite State Machines.

emmanueloga_ 7y ago

Statecharts _builds upon_ state machines, but is a more powerful language to model a system's state than FSMs or regular expressions. There's a good explanation here [1]. 1: https://stackoverflow.com/a/40679958/855105 https://stackoverflow.com/a/40679958/855105

dukoid 7y ago
What's their expressiveness? I always thought the nesting could be "flattened", so it wouldn't really make a difference?
- emmanueloga_ 7y ago
  Flattening the nested states would produce an explosion of states. This page describes how Statecharts avoids that [1]. In regard to expressivity, specially compared with FSM, a thorough description can be find in the paper "On Visual Formalisms" [2]. I copy some points here for convenience: ...people working on the design of really complex systems have all but given up on the use of conventional FSMs and their state diagrams for several reasons (1) State diagrams are “flat.” They provide no natural notion of depth, hierarchy, or modularity + orthogonality + broadcast communication. (2) State diagrams are uneconomical when it comes to transitions [...] resulting in an unnecessary multitude of arrows. (3) State diagrams are [...] infeasible: as the system under description grows linearly, the number of states grows exponentially. (4) State diagrams are inherently sequential in nature and do not cater for concurrency in a natural way. 1: https://statecharts.github.io/state-machine-state-explosion.html https://statecharts.github.io/state-machine-state-explosion.... 2: http://www.dcs.ed.ac.uk/home/kxt/on_visual_formalisms.pdf http://www.dcs.ed.ac.uk/home/kxt/on_visual_formalisms.pdf
- mcphage 7y ago
  State charts have parallel states, which require an exponential number of states with a finite state machine. And it supports history—returning to a container state can return to the last entered state in that container, whichever it was—I’m not sure if finite state machines can support that or not. Maybe they can, but again, it would vastly explode the state space.

deleted 7y ago

[deleted]

brucou 7y ago

State machines are a generic term. You will find here the different kinds of state machines, with varying expressive power that are used in computer science and actuak programming: https://github.com/achou11/state-machines https://github.com/achou11/state-machines In any case, keep in mind that Turing machines are (extended) state machines (albeit with infinite memory) so the expressive power of state machine is at least anything computable (sequentially - turing machine is a model of sequential computation).