# State-transition table

In automata theory and sequential logic, a state-transition table is a table showing what state (or states in the case of a nondeterministic finite automaton) a finite-state machine will move to, based on the current state and other inputs. It is essentially a truth table in which the inputs include the current state along with other inputs, and the outputs include the next state along with other outputs.
A state-transition table is one of many ways to specify a finite-state machine. Other ways include a state diagram.

## Common forms
### One-dimension

State-transition tables are sometimes one-dimensional tables, also called characteristic tables. They are much more like truth tables than their two-dimensional form. The single dimension indicates inputs, current states, next states and (optionally) outputs associated with the state transitions.
    State-transition table (S: state, I: input, O: output) InputCurrent stateNext stateOutput I$_1$S$_1$S$_i$O$_x$ I$_2$S$_1$S$_j$O$_y$ ………… I$_n$S$_1$S$_k$O$_z$ I$_1$S$_2$S$_{i′}$O$_{x′}$ I$_2$S$_2$S$_{j′}$O$_{y′}$ ………… I$_n$S$_2$S$_{k′}$O$_{z′}$ ………… I$_1$S$_m$S$_{i″}$O$_{x″}$ I$_2$S$_m$S$_{j″}$O$_{y″}$ ………… I$_n$S$_m$S$_{k″}$O$_{z″}$

### Two-dimensions

State-transition tables are typically two-dimensional tables. There are two common ways for arranging them.
In the first way, one of the dimensions indicates current states, while the other indicates inputs. The row/column intersections indicate next states and (optionally) outputs associated with the state transitions.
    State-transition table (S: state, I: input, O: output) InputCurrent stateI$_1$I$_2$…I$_n$ S$_1$ S$_i$/O$_x$S$_j$/O$_y$…S$_k$/O$_z$ S$_2$ S$_{i′}$/O$_{x′}$S$_{j′}$/O$_{y′}$…S$_{k′}$/O$_{z′}$ … ………… S$_m$ S$_{i″}$/O$_{x″}$S$_{j″}$/O$_{z″}$…S$_{k″}$/O$_{z″}$
In the second way, one of the dimensions indicates current states, while the other indicates next states. The row/column intersections indicate inputs and (optionally) outputs associated with the state transitions.
    State-transition table (S: state, I: input, O: output, —: illegal) Next stateCurrent stateS$_1$S$_2$…S$_m$ S$_1$ I$_i$/O$_x$—…— S$_2$ ——…I$_j$/O$_y$ … ………… S$_m$ —I$_k$/O$_z$…—

## Other forms

Simultaneous transitions in multiple finite-state machines can be shown in what is effectively an n-dimensional state-transition table in which pairs of rows map (sets of) current states to next states. This is an alternative to representing communication between separate, interdependent finite-state machines.
At the other extreme, separate tables have been used for each of the transitions within a single finite-state machine: "AND/OR tables" are similar to incomplete decision tables in which the decision for the rules which are present is implicitly the activation of the associated transition.

## Example

An example of a state-transition table together with the corresponding state diagram for a finite-state machine that accepts a string with an even number 0s is given below:
    State-transition table InputCurrent state 01 S$_1$ S$_2$S$_1$ S$_2$ S$_1$S$_2$
In the state-transition table, all possible inputs to the finite-state machine are enumerated across the columns of the table, while all possible states are enumerated across the rows. If the machine is in the state S$_1$ (the first row) and receives an input of 1 (second column), the machine will stay in the state S$_1$. Now if the machine is in the state S$_1$ and receives an input of 0 (first column), the machine will transition to the state S$_2$. In the state diagram, the former is denoted by the arrow looping from S$_1$ to S$_1$ labeled with a 1, and the latter is denoted by the arrow from S$_1$ to S$_2$ labeled with a 0. This process can be described statistically using Markov Chains.
For a nondeterministic finite-state machine, an input may cause the machine to be in more than one state, hence its non-determinism. This is denoted in a state-transition table by the set of all target states enclosed in a pair of braces. An example of a state-transition table together with the corresponding state diagram for a nondeterministic finite-state machine is given below:
    State-transition table InputCurrent state 01 S$_1$ S$_2$S$_1$ S$_2$ {S$_1$, S$_2$}S$_2$
If the machine is in the state S$_2$ and receives an input of 0, the machine will be in two states at the same time, the states S$_1$ and S$_2$.

## Transformations from/to state diagram

It is possible to draw a state diagram from a state-transition table. A sequence of easy to follow steps is given below:
* Draw the circles to represent the states given.
* For each of the states, scan across the corresponding row and draw an arrow to the destination state(s). There can be multiple arrows for an input character if the finite-state machine is nondeterministic.
* Designate a state as the start state. The start state is given in the formal definition of a finite-state machine.
* Designate one or more states as accepting state. This is also given in the formal definition of a finite-state machine.