Tabla de transición de estado

En teoría de autómatas y lógica secuencial, una tabla de transición de estados es una tabla que muestra a qué estado (o estados en el caso de un autómata finito no determinista) se moverá una máquina de estados finitos, en función de la situación actual. estado y otras entradas. Es esencialmente una tabla de verdad en la que las entradas incluyen el estado actual junto con otras entradas, y las salidas incluyen el siguiente estado junto con otras salidas.

Una tabla de transición de estados es una de las muchas formas de especificar una máquina de estados finitos. Otras formas incluyen un diagrama de estado.

Formas comunes

Unidimensional

Las tablas de transición de estado son a veces tablas unidimensionales, también llamadas tablas de características. Se parecen mucho más a tablas de verdad que a su forma bidimensional. La dimensión única indica entradas, estados actuales, estados siguientes y (opcionalmente) salidas asociadas con las transiciones de estado.

State-transition table
(S: estado, I: entrada, O: salida)

Input	Estado actual	Siguiente estado	Producto
I1	S1	Si	Ox
I2	S1	Sj	OSí.
...	...	...	...
In	S1	Sk	Oz
I1	S2	Si	Ox
I2	S2	Sj)	Oy
...	...	...	...
In	S2	Sk	Oz
...	...	...	...
I1	Sm	Si	Ox′′
I2	Sm	Sj'	Oy
...	...	...	...
In	Sm	Sk′	Oz

Dos dimensiones

Las tablas de transición de estado suelen ser tablas bidimensionales. Hay dos formas comunes de organizarlos.

En la primera forma, una de las dimensiones indica estados actuales, mientras que la otra indica entradas. Las intersecciones de fila/columna indican los siguientes estados y (opcionalmente) las salidas asociadas con las transiciones de estado.

State-transition table
(S: estado, I: entrada, O: salida)

Input Estado actual	I1	I2	...	In
S1	Si/Ox	Sj/OSí.	...	Sk/Oz
S2	Si/Ox	Sj)/Oy	...	Sk/Oz
...	...	...	...	...
Sm	Si/Ox′′	Sj'/Oz	...	Sk′/Oz

En la segunda forma, una de las dimensiones indica los estados actuales, mientras que la otra indica los siguientes estados. Las intersecciones de fila/columna indican entradas y (opcionalmente) salidas asociadas con las transiciones de estado.

State-transition table
(S: state, I: input, O: output, —: illegal)

Siguiente estado Estado actual	S1	S2	...	Sm
S1	Ii/Ox	—	...	—
S2	—	—	...	Ij/OSí.
...	...	...	...	...
Sm	—	Ik/Oz	...	—

Otras formas

Las transiciones simultáneas en múltiples máquinas de estados finitos se pueden mostrar en lo que efectivamente es una tabla de transiciones de estados n-dimensional en la que pares de filas asignan (conjuntos de) estados actuales a los siguientes estados. Esta es una alternativa para representar la comunicación entre máquinas de estados finitos interdependientes y separadas.

En el otro extremo, se han utilizado tablas separadas para cada una de las transiciones dentro de una única máquina de estados finitos: "tablas Y/O" son similares a tablas de decisión incompletas en las que la decisión para las reglas presentes es implícitamente la activación de la transición asociada.

Ejemplo

A continuación se muestra un ejemplo de una tabla de transición de estados junto con el diagrama de estado correspondiente para una máquina de estados finitos:

State-transition table

Input Estado actual	0	1
S1	S2	S1
S2	S1	S2

Diagrama de Estado

En la tabla de transición de estado, todas las entradas posibles a la máquina de estados finitos se enumeran en las columnas de la tabla, mientras que todos los estados posibles se enumeran en las filas. Si la máquina está en el estado S₁ (la primera fila) y recibe una entrada de 1 (segunda columna), la máquina permanecerá en el estado S₁. Ahora, si la máquina está en el estado S₁ y recibe una entrada de 0 (primera columna), la máquina pasará al estado S₂.
En el diagrama de estado, el primero se indica con la flecha que va de S₁ a S₁ etiquetada con un 1, y el segundo se indica con la flecha que va desde S₁ a S₂ etiquetados con un 0. Este proceso se puede describir estadísticamente utilizando cadenas de Markov.

Para una máquina de estados finitos no determinista, una entrada puede hacer que la máquina esté en más de un estado, de ahí su no determinismo. Esto se indica en una tabla de transición de estado mediante el conjunto de todos los estados objetivo encerrados entre un par de llaves {}. A continuación se proporciona un ejemplo de una tabla de transición de estados junto con el diagrama de estados correspondiente para una máquina de estados finitos no determinista:

State-transition table

Input Estado actual	0	1
S1	S2	S1
S2	#1, S2}	S2

Diagrama de Estado

Si la máquina está en el estado S₂ y recibe una entrada de 0, la máquina estará en dos estados al mismo tiempo, los estados S₁ y S₂.

Transformaciones desde/hacia diagrama de estados

Es posible dibujar un diagrama de estado a partir de una tabla de transición de estado. A continuación se proporciona una secuencia de pasos fáciles de seguir:

1. Dibuja los círculos para representar a los estados dados.
2. Para cada uno de los estados, escanear a través de la fila correspondiente y dibujar una flecha al estado de destino. Puede haber múltiples flechas para un personaje de entrada si la máquina de estado finito es no determinista.
3. Designar un estado como estado de inicio. El estado de inicio se da en la definición formal de una máquina de estado finito.
4. Designar uno o más estados como estado de aceptación. Esto también se da en la definición formal de una máquina de estado finito.