fbpx
Wikipedia

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.

Índice

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)

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

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.

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.
  • Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X

Tabla de transición de estados
tabla, transición, estados, idioma, vigilar, editar, teoría, autómatas, lógica, secuencial, tabla, transición, estados, tabla, muestra, qué, estado, moverá, autómata, finito, dado, basándose, estado, actual, otras, entradas, tabla, estados, esencialmente, tabl. Tabla de transicion de estados Idioma Vigilar Editar En teoria de automatas y logica secuencial una tabla de transicion de estados es una tabla que muestra que estado se movera un automata finito dado basandose 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 maquina de estados otras formas son un diagrama de estados y una ecuacion caracteristica Cuando se trata de un automata finito no determinista entonces la tabla de transicion muestra todos los estados que se movera el automata Indice 1 Formas comunes 1 1 Tablas de estados de una dimension 1 2 Tablas de Estados de dos dimensiones 2 Ejemplo 3 Transformaciones de a diagrama de estados 4 ReferenciasFormas comunes EditarTablas de estados de una dimension Editar Tambien llamadas tablas caracteristicas las tablas de estados de una dimension son mas 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 estan a la derecha Las salidas representaran el siguiente estado de la maquina Aqui hay un ejemplo sencillo de una maquina de estados con dos estados y dos entradas combinacionales A B Estado Actual Siguiente Estado Salida0 0 S1 S2 10 0 S2 S1 00 1 S1 S2 00 1 S2 S2 11 0 S1 S1 11 0 S2 S1 11 1 S1 S1 11 1 S2 S2 0 S1 y S2 representarian probablemente los bits individuales 0 y 1 dado que un simple bit solo tiene dos estados Tablas de Estados de dos dimensiones Editar Las tablas de transicion de estados son normalmente tablas de dos dimensiones Hay dos formas comunes para construirlas La dimension vertical indica los Estados Actuales la dimension horizontal indica eventos y las celdas intersecciones fila columna de la tabla contienen el siguiente estado si ocurre un evento y posiblemente la accion enlazada a esta transicion de estados Tabla de Transicion de Estados Events State E1 E2 EnS1 Ay Sj S2 Ax Si Sm Az Sk S estado E evento A accion transicion ilegal La dimension vertical indica los Estados Actuales la dimension horizontal indica los siguientes estados y las intersecciones fila columna contienen el evento el cual dirigira al siguiente estado particular Tabla de Transicion de Estados next current S1 S2 SmS1 Ay Ej S2 Ax Ei Sm Az Ek S estado E evento A accion transicion imposible Ejemplo EditarUn ejemplo de una tabla de transicion de estados para una maquina M junto con el correspondiente diagrama de estados esta dado abajo Tabla de Transicion de Estados Entrada Estado 1 0S1 S1 S2S2 S2 S1 Diagrama de estados Todas las entradas posibles a la maquina estan enumeradas a traves de las columnas de la tabla Todos los estados posibles estan enumerados a traves de las filas Desde la tabla de transicion de estados anterior es facil ver que si la maquina esta en S1 la primera fila y la siguiente entrada es el caracter 1 la maquina permanecera en S1 Si llega un caracter 0 la maquina realizara la transicion 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 automata finito no determinista AFND una nueva entrada puede causar que la maquina este en mas de un estado dado que es no determinista Esto se denota en una tabla de transicion de estados por un par de llaves con un conjunto de todos los estados objetivo entre ellos Se da un ejemplo abajo Tabla de Transicion de Estados para un AFND Entrada Estado 1 0 eS1 S1 S2 S3 FS2 S2 S1 FS3 S2 S1 S1 Aqui una maquina no determinista en el estado S1 leyendo una entrada de 0 causara que este en dos estados al mismo tiempo los estados S2 y S3 La ultima columna define la transicion legal de estados del caracter especial e Este caracter 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 ningun caracter de entrada Los dos casos anteriores configuran al automata finito no determinista Transformaciones de a diagrama de estados EditarEs posible dibujar un Diagrama de estados partiendo de la tabla Una secuencia posible de pasos a seguir es la siguiente Dibuja circulos que representen los estados dados Para cada uno de los estados mira la correspondiente fila y dibuja una flecha para cada uno de los estados destino Pueden ser multiples flechas para un mismo caracter de entrada si el automata es un AFND Designa un estado como el estado inicial El estado inicial esta dado en la definicion formal del automata Designa uno o mas estados como estado final o tambien llamado de aceptacion Esto tambien esta dado en la definicion formal Referencias EditarMichael Sipser Introduction to the Theory of Computation PWS Publishing Co Boston 1997 ISBN 0 534 94728 X Datos Q2303083Obtenido de https es wikipedia org w index php title Tabla de transicion de estados amp oldid 117371855, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos