Tabla de transición de estados

En teoría de autómatas y lógica secuencial, una tabla de transición de estados es una tabla que muestra qué estado se moverá un autómata finito dado, basándose en el estado actual y otras entradas. Una tabla de estados es esencialmente una tabla de verdad en la cual algunas de las entradas son el estado actual, y las salidas incluyen el siguiente estado, junto con otras salidas.

Una tabla de estados es una de las muchas maneras de especificar una máquina de estados, otras formas son un diagrama de estados, y una ecuación característica.

Cuando se trata de un autómata finito no determinista, entonces la tabla de transición muestra todos los estados que se moverá el autómata.

Formas comunes

Tablas de estados de una dimensión

También llamadas tablas características, las tablas de estados de una dimensión son más como tablas de verdad que como las versiones de dos dimensiones. Las entradas son normalmente colocadas a la izquierda, y separadas de las salidas, las cuales están a la derecha. Las salidas representarán el siguiente estado de la máquina. Aquí hay un ejemplo sencillo de una máquina de estados con dos estados, y dos entradas combinacionales:

A B Estado Actual Siguiente Estado Salida
0 0 S1 S2 1
0 0 S2 S1 0
0 1 S1 S2 0
0 1 S2 S2 1
1 0 S1 S1 1
1 0 S2 S1 1
1 1 S1 S1 1
1 1 S2 S2 0

S1 y S2 representarían probablemente los bits individuales 0 y 1, dado que un simple bit solo tiene dos estados.

Tablas de Estados de dos dimensiones

Las tablas de transición de estados son normalmente tablas de dos dimensiones. Hay dos formas comunes para construirlas.

  • La dimensión vertical indica los Estados Actuales, la dimensión horizontal indica eventos, y las celdas (intersecciones fila/columna) de la tabla contienen el siguiente estado si ocurre un evento (y posiblemente la acción enlazada a esta transición de estados).
Tabla de Transición de Estados
  Events
State
E1 E2   ...   En
S1 - Ay/Sj ... -
S2 - - ... Ax/Si
... ... ... ... ...
Sm Az/Sk - ... -

(S: estado, E: evento, A: acción, -: transición ilegal)

  • La dimensión vertical indica los Estados Actuales, la dimensión horizontal indica los siguientes estados, y las intersecciones fila/columna contienen el evento el cual dirigirá al siguiente estado particular.
Tabla de Transición de Estados
      next
current
S1 S2   ...   Sm
S1 Ay/Ej - ... -
S2 - - ... Ax/Ei
... ... ... ... ...
Sm - Az/Ek ... -

(S: estado, E: evento, A: acción, -: transición imposible)

Other Languages