Tabla de transición de estados

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 ) pasará una máquina de estados finitos , en función del estado actual y otras entradas. Esencialmente, se trata de 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 transiciones simultáneas en múltiples máquinas de estados finitos pueden representarse mediante una tabla de transición de estados n -dimensional, donde pares de filas asignan estados actuales (o conjuntos de ellos) 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 las 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 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 ceros:

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 S1 ₍ primera fila) y recibe una entrada de 1 (segunda columna), la máquina permanecerá en el estado S1 _. Ahora bien, si la máquina está en el estado S1 _y recibe una entrada de 0 (primera columna), la máquina pasará al estado S2 _. En el diagrama de estados, el primer caso se denota mediante la flecha que va de S1 _a S2 _etiquetada con un 1, y el segundo caso se denota mediante la flecha que va de S1 _a S2 _etiquetada con un 0. Este proceso se puede describir estadísticamente utilizando cadenas de Markov .

En una máquina de estados finitos no determinista , una entrada puede provocar que la máquina se encuentre en más de un estado, de ahí su no determinismo . Esto se representa en una tabla de transición de estados mediante el conjunto de todos los estados objetivo encerrados entre llaves {}. A continuación se muestra un ejemplo de 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 ₂ y recibe una entrada de 0, la máquina estará en dos estados al mismo tiempo, los estados S ₁ y S ₂ .

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 sencillos:

1. Dibuja círculos para representar los estados dados.
2. Para cada uno de los estados, recorra la fila correspondiente y dibuje una flecha hacia el estado o estados de destino. Puede haber varias flechas para un mismo carácter de entrada si la máquina de estados finitos no es determinista.
3. Designa un estado como estado inicial . El estado inicial se define formalmente como el de una máquina de estados finitos.
4. Designar uno o más estados como estados de aceptación . Esto también se especifica en la definición formal de una máquina de estados finitos.

• lista de adyacencia
• matriz de adyacencia
• Flujo de datos
• Tabla de excitación
• Máquina de estados finitos
• Notación de índice
• Máquina de Moore
• Máquina harinosa
• Metodología de Ward-Mellor

• Michael Sipser: Introducción a la teoría de la computación . PWS Publishing Co., Boston, 1997. ISBN 0-534-94728-X