En la teoría de autómatas y la 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 del estado actual 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 maneras de especificar una máquina de estados finitos . Otras maneras incluyen un diagrama de estados .
Las tablas de transición de estados son a veces tablas unidimensionales, también llamadas tablas características . Son mucho más parecidas a las tablas de verdad que su forma bidimensional. La dimensión única indica entradas, estados actuales, estados siguientes y (opcionalmente) salidas asociadas con las transiciones de estados.
Las tablas de transición de estados suelen ser tablas bidimensionales. Existen dos formas comunes de organizarlas.
En el primer caso, una de las dimensiones indica los estados actuales, mientras que la otra indica las entradas. Las intersecciones de filas y columnas indican los próximos estados y (opcionalmente) las salidas asociadas con las transiciones de estados.
En el segundo modo, una de las dimensiones indica los estados actuales, mientras que la otra indica los estados siguientes. Las intersecciones de filas y columnas indican las entradas y (opcionalmente) las salidas asociadas con las transiciones de estados.
Las transiciones simultáneas en múltiples máquinas de estados finitos se pueden mostrar en lo que es efectivamente una tabla de transición de estados n -dimensional en la que pares de filas asignan (conjuntos de) estados actuales a estados siguientes. [1] Esta es una alternativa para representar la comunicación entre máquinas de estados finitos separadas e interdependientes.
En el otro extremo, se han utilizado tablas separadas para cada una de las transiciones dentro de una única máquina de estados finitos: las "tablas AND/OR" [2] son similares a tablas de decisión incompletas en las que la decisión para las reglas que están presentes es implícitamente la activación de la transición asociada.
A continuación se muestra un ejemplo de una tabla de transición de estados junto con el diagrama de estados correspondiente para una máquina de estados finitos que acepta una cadena con un número par de 0:
En la tabla de transición de estados, 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 1 (la primera fila) y recibe una entrada de 1 (segunda columna), la máquina permanecerá en el estado S 1 . Ahora bien, si la máquina está en el estado S 1 y recibe una entrada de 0 (primera columna), la máquina pasará al estado S 2 .
En el diagrama de estados, el primero se denota por la flecha que va de S 1 a S 1 etiquetada con un 1, y el segundo se denota por la flecha que va de S 1 a S 2 etiquetada con un 0. Este proceso se puede describir estadísticamente utilizando cadenas de Markov .
En el caso de una máquina de estados finitos no determinista , una entrada puede hacer que la máquina se encuentre en más de un estado, de ahí su falta de determinismo . Esto se indica en una tabla de transición de estados mediante el conjunto de todos los estados de destino encerrados entre un par de llaves {}. A continuación se ofrece 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:
Si la máquina está en el estado S 2 y recibe una entrada de 0, la máquina estará en dos estados al mismo tiempo, los estados S 1 y S 2 .
Es posible dibujar un diagrama de estados a partir de una tabla de transición de estados. A continuación se muestra una secuencia de pasos fáciles de seguir: