Tabla de transición de estado - State-transition table

En la teoría de autómatas y la lógica secuencial , una tabla de transición de estado 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 , según el 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 formas de especificar una máquina de estados finitos. Otras formas incluyen un diagrama de estado .

Formas comunes

Una dimensión

Las tablas de transición de estado son a veces tablas unidimensionales, también llamadas tablas de características . Se parecen 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.

Tabla de transición de
estado (S: estado, I: entrada, O: salida)
Aporte Estado actual Siguiente estado Producción
Yo 1 S 1 S i O x
Yo 2 S 1 S j O y
... ... ... ...
Yo n S 1 S k O z
Yo 1 S 2 S i ′ O x ′
Yo 2 S 2 S j ′ O y ′
... ... ... ...
Yo n S 2 S k ′ O z ′
... ... ... ...
Yo 1 S m S i ″ O x ″
Yo 2 S m S j ″ O y ″
... ... ... ...
Yo n S m S k ″ O z ″

Dos dimensiones

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

De 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) salidas asociadas con las transiciones de estado.

Tabla de transición de
estado (S: estado, I: entrada, O: salida)
Aporte
Estado actual
Yo 1 Yo 2 ... Yo n
S 1 S i / O x S j / O y ... S k / O z
S 2 S yo ′ / O x ′ S j ′ / O y ′ ... S k ′ / O z ′
... ... ... ... ...
S m S i ″ / O x ″ S j ″ / O z ″ ... S k ″ / O z ″

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

Tabla de transición de
estado (S: estado, I: entrada, O: salida, -: ilegal)
Siguiente estado
Estado actual
S 1 S 2 ... S m
S 1 I i / O x - ... -
S 2 - - ... Yo j / O y
... ... ... ... ...
S m - Yo k / O z ... -

Otras formas

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 mapean (conjuntos de) estados actuales a los estados siguientes. Esta es una alternativa a la representación de la comunicación entre máquinas de estados finitos independientes e interdependientes.

En el otro extremo, se han utilizado tablas separadas para cada una de las transiciones dentro de una sola máquina de estados finitos: las "tablas Y / O" son similares a las tablas de decisión incompletas en las que la decisión de las reglas que están 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 estados correspondiente para una máquina de estados finitos:

Tabla de transición de estado
Aporte
Estado actual
0 1
S 1 S 2 S 1
S 2 S 1 S 2
Diagrama de estado
Diagrama de estado de FSM

En la tabla de transición de estado, todas las posibles entradas 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, 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 estado, el primero se denota con la flecha que va de S 1 a S 1 etiquetada con un 1, y el último se denota con la flecha de S 1 a S 2 etiquetada con un 0. Este proceso se puede describir estadísticamente usando 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 denota en una tabla de transición de estado por el conjunto de todos los estados objetivo encerrados en un par de llaves {}. A continuación se muestra un ejemplo de una tabla de transición de estado junto con el diagrama de estado correspondiente para una máquina de estados finitos no determinista:

Tabla de transición de estado
Aporte
Estado actual
0 1
S 1 S 2 S 1
S 2 {S 1 , S 2 } S 2
Diagrama de estado
Diagrama de estado de NFSM

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 .

Transformaciones de / a diagrama de estados

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:

  1. Dibuja los círculos para representar los estados dados.
  2. Para cada uno de los estados, escanee la fila correspondiente y dibuje una flecha hacia los estados de destino. Puede haber varias flechas para un carácter de entrada si la máquina de estados finitos no es determinista.
  3. Designe un estado como estado de inicio . El estado de inicio se da en la definición formal de una máquina de estados finitos.
  4. Designe 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 estados finitos.

Ver también

Referencias

Otras lecturas

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