Máquina de estados
De Wikipedia, la enciclopedia libre
Saltar a navegación, búsqueda
Se ha sugerido que este artículo o sección sea fusionado con Autómata finito (ver la discusión al respecto).Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales en WP:TAB/F. |
Se denomina máquina de estados a un modelo de comportamiento de un sistema con entradas y salidas, en donde las salidas dependen no sólo de las señales de entradas actuales sino también de las anteriores. Las máquinas de estados se definen como un conjunto de estados que sirve de intermediario en esta relación de entradas y salidas, haciendo que el historial de señales de entrada determine, para cada instante, un estado para la máquina, de forma tal que la salida depende únicamente del estado y las entradas actuales.
Una máquina de estados se denomina máquina de estados finitos (FSM por finite state machine) si el conjunto de estados de la máquina es finito, este es el único tipo de máquinas de estados que podemos modelar en un computador en la actualidad; debido a esto se suelen utilizar los terminos máquina de estados y máquina de estados finitos de forma intercambiable. Sin embargo un ejemplo de una máquina de estados infinitos seria un computador cuántico esto es debido a que los Qubit que utilizaría este tipo de computadores toma valores continuos, en contraposición los bits toman valores discretos (0 ó 1). Otro buen ejemplo de una máquina de estados infinitos es una Máquina universal de Turing la cual se puede definir teóricamente con una "cinta" o memoria infinita.
La representación de una máquina de estados se realiza mediante un Diagrama de estados, sin embargo también es posible utilizar un Diagrama de flujo.
Es posible clasificar las máquinas de estados en aceptoras o transductoras:
- Aceptoras (también llamadas reconocedoras o discriminadoras): Son aquellas en donde la salida es binaria (si/no), depende únicamente del estado y existe un estado inicial. Puede decirse, entonces, que cuando la máquina produce una salida "positiva" (es decir, un "si"), es porque ha "reconocido" o "aceptado" la secuencia de entrada. En las máquinas de estados aceptoras, los estados con salida "positiva" se denominan estados finales.
- Transductoras: Son las más generales, que convierten una secuencia de señales de entrada en una secuencia de salida, pudiendo ésta ser binaria o más compleja, depender de la entrada actual (no sólo del estado) y pudiendo también prescindirse de un estado inicial.
La bibliografía a veces llama autómata finito a las aceptoras, mientras que en otros casos se emplea autómata como sinónimo de máquina de estados sin importar su tipo.
Las aceptoras son los de mayor interés en la Teoría de la Computación, más precisamente en la Teoría de autómatas, siendo éstas ramas de la matemática. Las transductoras, en cambio, lo son en la electrónica digital y la computación práctica. Es por eso que, por lo general, en los textos sobre matemática y ciencias de la computación se suele hablar de autómatas (y se refieren a las aceptoras) mientras que los de electrónica y computación práctica hablan de máquinas de estados (y se refieren a los transductoras).
En UML(Lenguanje Unificado de Modelado), Dice que una maquina de estado es aquel comportamiento, que permite hacer un seguimiento de la vida de un objeto en el transcurso de un tiempo finito
Modelo de una maquina de estado finito
La maquina lee una secuencia de símbolos de entrada que están almacenados en una cinta de entrada y almacena una secuencia de símbolos de salida en una cinta de salida. Supóngase que la maquina se encuentra en un estado SI y que lee sus símbolos de entrada a1 en una cabeza de lectura. Se aplica entonces la transformación l causando así que la cabeza de escritura registre un símbolo ok en la cinta de la salida. La función d hace que la maquina entre en el estado SJ. La maquina procede a leer el siguiente símbolo de entrada y continua su operación hasta que se hayan procesado todos los símbolos en la cinta de entrada.
Ejemplo: lo siguiente define una maquina de estado finito con 2 símbolos de entrada, 3 estados internos y 3 símbolos de salida.
I={a,b}
S={q0,q1,q2}
O={x,y,z}
NOTA: es tradicional usar la letra q para los estados de la maquina y usar el símbolo q0 para el estado inicial.
ACTIVIDADES OBLIGATORIAS
- Las maquinas de estado finito están compuestas de 5 elementos, relacione cada uno de estos elemento con algún objeto que utilice cotidianamente y describa su funcionamiento.
ACTIVIDADES SUGERIDAS
- Mencione que relación tienen las maquinas de estado finito con las gramáticas y los lenguajes formales.
RECURSOS PARA AMPLIAR EL TEMA
AUTOEVALUACION
- En un compilador mencione que representan los símbolos de entrada, estados internos y símbolos de salida.
Dos máquinas finitas se comportan como una conectada a un bus infinito: .... Es una cómoda caracterización de la máquina que regula la frecuencia, ... | |
Todos los sistemas, como las máquinas finitas, pueden ser controlados por una fuente sincronizadora. Esta fuente, se da gracias a un evento llamado se˜nal ... | |
sistema aritmético tampoco puede ser probada en los límites de la lógica finita permitida. Esto es algo así como que las “máquinas finitas” que contienen ... | |
Máquinas finitas de estado. Tiempo de propagación o retardo del biestable (delay time) ... Máquinas finitas de estado. Anchura del reloj tWH y tWL ... | |
Taller de maquinas de estado finitas. 1. A continuación se listará el codigo en VHDL del ejercicio maquina de Moore desarrollado en clase(una versión ... | |
2.7 Problemas en el diseño de máquinas finitas de estado borrosas. ..... Paso 2: Procesamiento de las trazas mediante la máquina finita de estados borrosa. ... | |
posible hablar de dos tipos diferentes de máquinas de estado finitas: Máquina de Moore. Máquina de Mealy. Estado Siguiente = F(Estado Actual, Entrada) ... | |
Registros, contadores y máquinas finitas de estados. 1.1. Ejemplos de registros. 1.1.1. Registros de almacenamiento paralelo. Son los más frecuentes, ... |
No hay comentarios:
Publicar un comentario