|
Tabla de transición de estadosEn 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 comunesTablas de estados de una dimensiónTambié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:
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 dimensionesLas tablas de transición de estados son normalmente tablas de dos dimensiones. Hay dos formas comunes para construirlas.
(S: estado, E: evento, A: acción, -: transición ilegal)
(S: estado, E: evento, A: acción, -: transición imposible) EjemploUn ejemplo de una tabla de transición de estados para una máquina M junto con el correspondiente diagrama de estados está dado abajo.
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.
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 estadosEs posible dibujar un Diagrama de estados partiendo de la tabla. Una secuencia posible de pasos a seguir es la siguiente:
Referencias
|
Portal di Ensiklopedia Dunia
