Skip to content

What's FSA?

Jump to bottom
pavl_g edited this page Aug 10, 2023 · 5 revisions

Finite-State-Automaton is represented as sequential states of logic, between every 2 states, a transition exists, a transition defines transiting from state A to state B, and each state processes an input (associated with the transition) and is capable of producing an output (defined by the present-state).

Here is a simple diagram describing a Finite-State-Automaton in action, this is a deterministic FSA (each state accepts only and only one successor transition):

image

  • State-A: is the binary addition non-carry state, it carries zero (0) as a default value.
  • State-B: is the binary addition carry state, it carries one (1) as a default value.

Here is a tabulation form of the solution for this simple FSA pattern (Serial Adder):

Present State Inputs of transition Output of the present state Next Assigned State (based on the output)
State-A (Non-carry) (0, 0) 0 State-A (Non-carry state)
State-A (Non-carry) (0, 1) 1 State-A (Non-carry state)
State-A (Non-carry) (1, 0) 1 State-A (Non-carry state)
State-A (Non-carry) (1, 1) 0 State-B (Carry State)
State-B (Carry State) (0, 1) 1 (Because a carry state holds an additional (1) carry by default) State-B (Carry State)
State-B (Carry State) (1, 0) 1 (Due to an additional (1) provided by the present state) State-B (Carry State)
State-B (Carry State) (1, 1) 0 (Due to an additional (1) provided by the present state) State-B (Carry State)
State-B (Carry State) (0, 0) 1 (Due to an additional (1) provided by the present state) State-A (Non-Carry State)

Note: The next assigned state is directed from the output of the present state, the output can be validated using a transitional listener via a transitional manager instance (Command-State Strategy pattern).

Finite-State-Automaton Components:

  • A Transition: composed of a present state, a next state, and an input value aka. the successor value or the transition value.

  • A Transitional Manager: manages and handles the transition paths in an FSA environment.

  • Transitional Listeners: embedded Command-State pattern to inject some actions in-between the FSA transitions, this pattern can assign new transitions to the system.

Note: FSA is an abstract concept and can be applied to any type of logic (e.g., GUI - Embedded Systems - Game Engines - Compilers).

Clone this wiki locally