Tabla de transición de estados

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 que estado (o estados en el caso de un Autómata finito no determinista) se moverá la máquina de estados, 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.

Contenido

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)

Ejemplo

Un ejemplo de una tabla de transición de estados para una máquina M junto con el correspondiente diagrama de estados está dado abajo.

Tabla de Transición de Estados
  Entrada
Estado
1 0
S1 S1 S2
S2 S2 S1
  Diagrama de estados
DFAexample.svg

Todas las entradas posibles a la máquina están enumeradas a través de las columnas de la tabla. Todos los estados posibles están enumerados a través de las filas. Desde la tabla de transición de estados anterior, es fácil ver que si la máquina está en S1 (la primera fila), y la siguiente entrada es el carácter 1, la máquina permanecerá en S1. Si llega un carácter 0, la máquina realizará la transición a S2 como puede verse desde la segunda columna. En el diagrama esto es denotado por la flecha desde S1 a S2 etiquetada con un 0.

Para un autómata finito no determinista (AFND), una nueva entrada puede causar que la máquina esté en más de un estado, dado que es no determinista. Esto se denota en una tabla de transición de estados por un par de llaves { } con un conjunto de todos los estados objetivo entre ellos. Se da un ejemplo abajo.

Tabla de Transición de Estados para un AFND
  Entrada
Estado
1 0 ε
S1 S1 { S2, S3 } Φ
S2 S2 S1 Φ
S3 S2 S1 S1

Aquí, una máquina no determinista en el estado S1 leyendo una entrada de 0 causará que esté en dos estados al mismo tiempo, los estados S2 y S3. La última columna define la transición legal de estados del carácter especial, ε. Este carácter especial permite a los AFND moverse a un estado diferente cuando no hay ninguna entrada. En el estado S3, el AFND puede moverse a S1 sin consumir ningún carácter de entrada. Los dos casos anteriores configuran al autómata finito no determinista.

Transformaciones de/a diagrama de estados

Es posible dibujar un Diagrama de estados partiendo de la tabla. Una secuencia posible de pasos a seguir es la siguiente:

  1. Dibuja círculos que representen los estados dados.
  2. Para cada uno de los estados, mira la correspondiente fila y dibuja una flecha para cada uno de los estados destino. Pueden ser múltiples flechas para un mismo carácter de entrada si el autómata es un AFND.
  3. Designa un estado como el estado inicial. El estado inicial está dado en la definición formal del autómata.
  4. Designa uno o más estados como estado final( o también llamado de aceptación). Esto también está dado en la definición formal.

Referencias

  • Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Tabla (desambiguación) — Saltar a navegación, búsqueda Contenido 1 Información 2 Deporte 3 Además 4 Véase también …   Wikipedia Español

  • Transición — Una transición es la acción y efecto de pasar de un modo de ser o estar, a otro muy distinto del anterior. Representa un cambio de un estado a otro. En ciencias sociales: 1carlos cerrato Transición política, entendida normalmente como transición… …   Wikipedia Español

  • Tabla — Se ha sugerido que Tablas sea fusionado en este artículo o sección (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí. El término tabla puede referirse a: Un modo de organizar la información,… …   Wikipedia Español

  • Estados miembros y organización territorial de la Unión Europea — Este artículo o sección sobre geografía y política necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 1 …   Wikipedia Español

  • Metal de transición — Los metales de transición o elementos de transición son aquellos elementos químicos que están situados en la parte central del sistema periódico, en el bloque d, cuya principal característica es la inclusión en su configuración electrónica del… …   Wikipedia Español

  • Transductor de estados finitos determinista p-subsecuencial adelantado — Los transductores de estados finitos son Autómatas de estados finitos deterministas con transiciones sobre parejas de símbolos. Un transductor de estados finitos determinista p subsecuencial adelantado (TpSSDA o EDpSST de sus siglas en inglés… …   Wikipedia Español

  • Autómata finito — Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de… …   Wikipedia Español

  • OpenType — Desarrollador Microsoft y Adobe Systems Información general Extensión de archivo .otf, .ttf Type code …   Wikipedia Español

  • Elemento químico — Tabla periódica de los elementos químicos. Un elemento químico es un tipo de materia, constituida por átomos de la misma clase. En su forma más simple posee un número determinado de protones en su núcleo, haciéndolo pertenecer a una categoría… …   Wikipedia Español

  • Máquina de Turing — Para otros usos de este término, véase Turing (desambiguación). Una máquina de Turing (MT) es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. Este …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”