State Machine

A state machine is a description of a process (computational, physical, economic) in terms of its potential sequences of states.

The state of a system is defined to be all we need to know about the system to predict its future trajectories as well as possible. For example, it could be the position and velocity of an object or the locations of your pieces on a game board, or the current traffic densities on a highway network.

Formally, we define a state machine as $(S,X,Y,s_0,f,q)$, where:

• $S$ is set of states
• $X$ is set of inputs
• $Y$ is set of outputs
• $s_0\in S$ is the initial state of the machine
• $f:S\times X\to S$ is a transition function, which takes an input and a previous state and produces a next state. This can be more clearly written as $f(s_t,x_t)=s_{t+1}$.
• $g:S\to Y$ is an output function, which takes a state and produces an output.

The basic operation of the state machine is to start with $s_0$, then iteratively compute $t\ge 1$:

$$\begin{array}{rl}{s}_t& =f(s_{t-1},x_t)\\ y_t& =g(x)\end{array}$$

The diagram below illustrates this process:

• Note that the “feedback” connection of $s_t$ back into $f$ has to be buffered or delayed by one time step – otherwise, what it is computing would not generally be well defined.

So, given a sequence of inputs $x_1,x_2,\dots$ the machine generates a sequence of outputs

$$\underset{y_1}{\underbrace{g(f(s_0,x_1))}},\underset{y_2}{\underbrace{g(f(f(s_0,x_1),x_2))}},\dots$$

We sometimes say machine transduces sequences $x$ into sequence $y$. The output at time $t$ can have dependence on inputs from steps $1$ to $t$.

Finite state machines can be described using a State Transition Diagram.