UNIVERSIDAD NACIONAL DE
SAN AGUISTIN
CURSO:
MATEMATICAS DISCRETAS
TEMA:
APLICACION DE MAQUINAS DE ESTADO
FINITO A LA ING. ELECTRICA
DOCENTE:
CARDENAS RIVERA MARIA
PRESENTADO POR:
HUAMANI HUAMANI ALEX ANDERSON CUI 20123695
TONCONI CONDORI WIDO SAUL CUI 20123693
AREQUIPA-2022
MÁQUINAS DE ESTADOS FINITOS
INTRODUCCIÓN
En general, los circuitos secuenciales pueden clasificarse en dos tipos; (1) aquellos
en los que la salida o salidas depende únicamente del estado interno actual
(denominados circuitos de Moore) y (2) aquellos en los que la salida o salidas
depende tanto del estado actual como de la entrada o entradas (denominados
circuitos de Mealy).
OBJETIVOS
• La aplicación de flip flops a una máquina de estados con el fin de
comprender sus posibles aplicaciones en sistemas digitales.
• Desarrollar un diagrama de estados para una determinada
secuencia.
• Desarrollar una tabla del estado siguiente para una secuencia de
contador especifica.
• Implementar un contador para generar una secuencia de estados
especifica.
RESUMEN
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 términos máquina de estados y máquina de estados finitos
de forma intercambiable. Sin embargo un ejemplo de una máquina de estados
infinitos sería un computador cuántico esto es debido a que los Qubit que utilizaría
este tipo de computadores toman 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.
MARCO TEÓRICO
MÁQUINA DE ESTADO FINITO:
Una Máquina de Estado Finito (Finite State Machine), llamada también Autómata Finito es una
abstracción computacional que describe el comportamiento de un sistema reactivo mediante un
número determinado de Estados y un número determinado de Transiciones entre dicho Estados.
Las Transiciones de un estado a otro se generan en respuesta a eventos de entrada externos e
internos; a su vez estas transiciones y/o subsecuentes estados pueden generar otros eventos de
salida. Esta dependencia de las acciones (respuesta) del sistema a los eventos de entrada hace que las
Máquinas de Estado Finito (MEF) sean una herramienta adecuada para el diseño de Sistemas
Reactivos y la Programación Conducida por Eventos (Event Driven Programming), cual es el caso de la
mayoría de los sistemas embebidos basados en microcontroladores o microprocesadores.
Las MEF se describen gráficamente mediante los llamados Diagramas de Estado Finito (DEF), llamados
también Diagramas de Transición de Estados.
Máquinas de estados finitos se utilizan ampliamente en aplicaciones en ciencias de la computación y
redes de datos.
Por ejemplo, las máquinas de estados finitos son la base para los programas de corrección ortográfica,
la comprobación de la gramática, la indexación o la búsqueda de grandes volúmenes de texto,
reconocimiento de voz, la transformación de texto utilizando lenguajes de marcado como XML y
HTML, y los protocolos de red que especifican cómo las computadoras se comunican
Definición
Son ciertos circuitos secuenciales que tiene un número determinado de estado
(2n) . Pueden ser retroalimentados (flip flops, biestables) o maquinas
sincrónicas temporizadas cuando utilizan las primeras para crear circuitos cuyas
entradas son examinadas y cuyas salidas cambian con respecto a una señal de reloj
controlada. En cualquier caso, se tienen unas entradas, unas salidas y unos
estados.
Estructura
Fig.1 Estructura máquina de estados sincronizada por reloj (Mealy)
• Lógica de estado siguiente (F): Una función de las entradas y del estado
actual.
• Memoria de estados: es un conjunto de n flip flops que almacenan el
estado presente de la máquina, que tiene 2n estados diferentes. La señal
de reloj controla el cambio de estado en tales flip flops.
• La señal de reloj: dispone el funcionamiento de los flip flops ya sea por
disparo por flanco o por disparo de pulso.
• Lógica de salida (G): una función del estado actual y/o de lasentradas.
Máquina de Mealy
Es la máquina de estado en la cual la salida depende tanto del estadopresente
como de las entradas externas (es representado en la figura 1).
Máquinas de Moore
Es la máquina de estado en la cual las salidas solo dependen del estadopresente.
Su estructura se muestra en la figura 2.
Fig.2 Estructura máquina de Moore
Tabla 1 Diferencia entre máquina de Mealy y de Moore
MATERIALES
• 74LS76.
• 74LS266.
• 74LS08.
• 74LS04.
• Led’s
• Dipswitch.
IMPLEMENTACIÓN
1. Máquina de estado Mealy
Figura 3
Mapa de estados:
Tabla 2
EST X1 X0 Qn Y J1 K1 Qn
1
0 0 0 0 0 1 0 1
1 0 0 1 1 1 0 1
2 0 1 0 1 0 0 0
3 0 1 1 0 0 0 1
4 1 0 0 1 0 0 0
5 1 0 1 0 0 0 1
6 1 1 0 0 0 1 0
7 1 1 1 1 0 1 0
Diagrama de flujo
Figura 4
2. Máquina de estado Moore
Mapa de estados
Tabla 3
EST X1 X0 Q2 Qn Y J2 K2 J1 K1 Q2n Qn
n 1 1
0 0 0 0 0 0 0 1 1 0 0 1
1 0 0 0 1 0 1 0 1 0 1 1
2 0 0 1 0 1 0 1 1 0 0 1
3 0 0 1 1 1 1 0 1 0 1 1
4 0 1 0 0 0 1 0 0 0 1 0
5 0 1 0 1 0 0 0 0 0 0 1
6 0 1 1 0 1 1 0 0 0 1 0
7 0 1 1 1 1 0 0 0 0 1 1
8 1 0 0 0 0 1 0 0 0 1 0
9 1 0 0 1 0 0 0 0 0 0 1
10 1 0 1 0 1 1 0 0 0 1 0
11 1 0 1 1 1 0 0 0 0 1 1
12 1 1 0 0 0 0 1 0 1 0 0
13 1 1 0 1 0 1 0 0 1 1 0
14 1 1 1 0 1 0 1 0 1 0 0
15 1 1 1 1 1 1 0 0 1 1 0
Diagrama de flujo
Figura 6
VENTAJAS DE LAS MÁQUINAS DE ESTADO FINITO
• Son intuitivas y fáciles de entender.
• Abstraen convenientemente detalles secundarios que no son necesarios para el
análisis del sistema a un alto nivel y se centran en aspectos claves del mismo.
• Aportan un componente visual que facilita el análisis y diseño del sistema.
• Son universalmente aplicables.
• Su uso es común un sistemas de transmisión de datos y el uso de protocolos de
comunicación.
• En programación minimiza grandemente la tendencia a escribir "código espagueti" y
puede ayudar a reducir la cantidad de variable globales necesarias, aumentando al
mismo tiempo la confiabilidad del sistema.
DESVENTAJAS DE LAS MÁQUINAS DE ESTADO FINITO
• No son aplicables a todos los problemas de diseño.
• Funcionan bien en sistemas pequeños con una cantidad de estados en el orden de las
decenas.
• No funcionan bien en sistemas con una cantidad de estados en el orden de las
centenas o miles de estados, aunque en estos casos es posible la estructuración
mediante una combinación de MEFs más pequeñas.
• La adición de funcionalidad es un poco inflexible.
• Son "planas" por naturaleza, no poseen estructura definida y no permiten una
jerarquización de los componentes que minimize la repetición innecesaria de ciertos
estados. Una mejor alternativa en este caso es el uso de las Cartillas de Estado
(Statecharts) y el uso de UML (Unified Modelling Language).
• Es fácil caer en el error de definir demasiados estados para el sistema, lo cual
minimiza la eficiencia, o de definir menos estados de lo que es necesario, lo cual
contradice al propósito de las MEFs de reducir la cantidad de código convolucionado
(demasiadas sentencias condicionales del tipo "if - then - else").
OBSERVACIONES Y CONCLUSIONES
• Empezamos con una definición de máquina de estados finitos, aprendiendo que puede ser
usada como técnica de control en un sistema, describiendo los estados o comportamientos
de ese sistema, y definiendo reglas o condiciones que gobiernan transiciones del estado
actual del sistema a otroestado.
• Las Maquinas de estados Finitos, nos sirven para realizar procesos bien definidos en un
tiempo discreto. Reciben una entrada, hacen un proceso y nos entregan una salida. Notemos
que estas máquinas hacen una computación.
• Por esta misma razón es que a lo largo de la investigación les presentamos una variedad de
máquinas que tienen mucha relación y que pueden resolver un estado finito.
• Por lo tanto una computación es capaz de resolver un problema, sí y solo sí tiene una solución
algorítmica, es decir, puede ser descrito mediante una secuencia finita de pasos bien
definidos un claro ejemplo es la máquina de Turing.
• Podemos decir que cualquier solución a un problema que pueda ser representada por una
Maquina de Turing está haciendo una computación. Si una máquina imprime dos tipos de
símbolos, donde el primer tipo (llamadas figuras) consiste íntegramente en 1 y 0 y el segundo
tipo serán llamados símbolos de la segunda especie entonces podemos llamar a esa máquina
computadora.
BIBLIOGRAFIA
• Ronald J. Tocci. Sistemas digitales, principios y aplicaciones.Biblioteca UDB.
• Thomas Floyd. Fundamentos de sistemas digitales. 9° edición.
• Morris Mano. Diseño digital. 1° Edición. Editorial Prentice Hail.Biblioteca UDB.
• Aleksander, F. Hanna. “Automata Theory: An Engineering
• Approach”. Computer Systems Engineering Series. Crane, Russak & Company, New York,
1975.
• M. Simon. “Automata Theory”. World Scientific, 1999
• G. Berry, R. Sethi. “From Regular Expressions to Deterministic automata” Theoretical
Computer Science. Vol. 48. pp. 117-126. 1987.
• R. Kain. “Automata Theory: Machines and Languages”. McGrawHill, New York, 1972.
• Z. Kohavi. “Switching and Finite Automata Theory”. McGraw-Hill, New York, 1970.
