presentacion 2 - maquinas de estado finito
Post on 24-Jun-2015
28.206 Views
Preview:
DESCRIPTION
TRANSCRIPT
Andrea Peña José Valentín
Antonio Cabán Xaymara Pérez
Las máquinas de estado finitos son:
• modelos de comportamiento de un sistema o un
objeto complejo, con un número limitado de modos o
condiciones predefinidos, donde existen transiciones
de modo.
• modelo matemático que realiza computos de forma
automática sobre una entrada para producir una
salida.
• Modelo que posee sintaxis y semántica formales y
que sirve para representar aspectos dinámicos
que no se expresan en otros diagramas.
• una herramienta muy útil para especificar
aspectos relacionados con tiempo real, puede ser
electrónico o computacional o de otro tipo como
circuitos, arquitecturas de software, etc.
Una maquina de estado finito se compone de un número finito de estados y transiciones entre los estados.
Las máquinas de estado finito se descirben como:M = (S,∑, A , sk)
Donde S = {s1, s2, ….,sm } es un conjunto finito de nodos ∑ es un alfabeto infinito de etiquetas A es un conjunto de aristas etiquetadas que unen los
nodos sk es el estado inicial
Los nodos representan los posibles estados.Las etiquetas representan eventos que
provocan un cambio. Las aristas determinan de qué manera cada
estado, dado un evento, se dirige a otro estado.
a b
b
a 1
2
3
Cuando describimos la máquina en palabras es similar a cuando realizamos el algoritmo de un programa, hay que escribir en detalle todo lo que queremos que realice esta máquina sin obviar comandos o decisiones que debe tomar.
El diagrama es una parte importante ya que este nos ayudará a entender las funciones de la máquina de estado finito que queremos construir.
El diagrama que dibujemos debe contener todas las posibles entradas y salidas que nuestra máquina tiene o sea estados y valores que va ha realizar.
Necesitamos representar los valores en nuestro diagrama como números binarios para luego poder representarlos en un circuito.
Además vamos a cambiar los nombres que le dimos en el diagrama a los valores por los números que acabamos de sustituir.
Al realizar la tabla de verdad tenemos que tomar la data del diagrama de la máquina de estado finito.
Esto nos ayudará a determinar si nuestro diagrama está correctamente construido.
Tenemos que dibujar nuestra máquina de estado finito en un circuito el cual vamos a ir modificando según se simplifica el algoritmo de la misma.
Este circuito a su vez puede tener sub-circuitos dentro del mismo para distintas funciones, o comandos de la máquina.
Para cada sub-circuito que necesitamos diseñar, vamos a escribir una expresión lógica que expresa su salida en función de sus entradas. Derivamos las expresiones de la tabla de verdad que escribimos en el paso 4.
A esta expresión se le llama expresión booleana.
Para dibujar el resto del circuito necesitamos la expresiones booleanas y el circuito inicial.
Ahora les mostraremos un ejemplo de una máquina de estado finito y como se construye.
Este ascensor solo funcionara del piso tierra al 1er piso y viceversa.
Este estará compuesto con 2 botones uno para subir al piso 1ero y el otro para llegar a tierra, también tiene 2 luces que encienden, cuando esta roja esta en el piso tierra y cuando esta verde esta en el 1er piso.
¿ Que orden necesitamos tener?
Control de Ascensor Up
Down Down
Down
TierraROJO ON,
VERDE OFF
1 er PISOROJO OFF,
VERDE ON
Control de Ascensor 1 0
0
0
0ROJO =1, VERDE
=0
1ROJO = 0,
VERDE =1
Current
State
Input Next State
Rojo Verde
0 0 0 1 0
0 1 1 1 0
1 0 0 0 1
1 1 1 0 1
I
R CS NS CS clk
G
OutputSub-
Circuit
Next-StateSub-
Circuit
DFlipFlop
(DELAY)
Este circuito contiene los sub-circuitos
R
I CS NS CS clk
G
Next-StateSub-
Circuit
DFlipFlop
(DELAY)
Sub-Circuit for Red
Sub-Circuit
for Green
Recordamos que para cada sub-circuito tenemos una expresión.
Para el “Next State ”sub-circuito tenemos dos entradas y una salida, y si vamos a la tabla de verdad en solo dos casos el NS =1.
1. CS=0 y I=12. CS=1 y I=1
De aquí cuando lo simplificamos obtenemos que NS=I, y de la misma manera, R= “not” CS y G= CS
Por lo tanto las expresiones booleanas son:1. NS = I2. R = not CS3. G= CS
I
R CS NS CS clk
G
DFlip
Flop
(DELAY)
Esto lo podemos realizar para cualquier máquina de estado finito.
Entre las máquinas de estado finito disenadas especialmente para el reconocimiento de lenguajes, están los autómatas de estado finito (máquinas de estado finito sin salida).
Los autómatas de estado finito tienen un interés especial, debido a su relación con los lenguajes.
Definición:
Un automata de estado finito A = (I, O, S, f, g, σ) es una máquina de estado finito en la que el conjunto de símbolos de salida es {0,1} y donde el estado actual determina la última salida.
Aquellos estados para los cuales la última salida es 1 son los estados de aceptación.
Formalmente, un autómata finito determinista (AFD) es similar a un Autómata de estados finitos, representado con una 5-tupla (S,Φ,T,s,A) donde:
1. Ф un conjunto finito de símbolos de entrada llamado alfabeto
2. S un conjunto finito de estados 3. T es una transición de la función 4. s es el estado inicial (que pertenezca al
conjunto finito de estados) 5. A es un subconjunto de estados de aceptación o
finales.
Es una máquina de estados finitos, donde para cada par de estado y símbolo de la entrada puede haber varios estados próxima posible.
Esto lo distingue de los autómatas finitos deterministas (DFA), de ser posible únicamente es el estado de los próximos determinado.
Por cada símbolo de entrada que éste pase a un nuevo estado hasta que todos los símbolos de entrada se han consumido.
Se puede representar usando tablas de estado o diagramas
Un autómata finito no determinista también puede o no tener más de un nodo inicial.
Si M = (S,I,f,s,F) consiste en: 1.Un conjunto finito de estados S.2.Un alfabeto de entrada finito I.3.Una función de transición f que asigna a cada
pareja de estado y entrada, un conjunto de estados
4.Un estado inicial s.5.Un subconjunto de S con los estados finales
denominado F.
Un AFND es aquel que presenta cero, una o más transiciones por el mismo carácter del alfabeto .
Dos tipos de Transductores:1.Maquina de MooreEs un automata de estado finito donde las
salidas son determinadas por el estado corriente solo (y no por la entrada).
El diagrama incluye una señal de salida para cada estado.
Utiliza solo acciones de entrada, la salida depende solamente del estado.
La ventaja es la simplificación del comportamiento
Reconoce dos comandos: “comando_abrir o encendido” y “comando_cerrar o apagado” que disparan la alteración de estado.
La siguiente imagen es un ejemplo del mismo
2. Máquina de Meadley:A diferencia de una máquina de Moore , esta
es un tipo de máquina de estados finitos donde las salidas se generan como producto de la transición entre los estados. En el siguiente ejemplo, la luz se ve afectada por el proceso de cambios de estado.
Relación de Grafos y
Máquinas de Estado Finito
Los grafos son artefactos matemáticas que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole.
Un grafo esta formado por dos conjuntos:
* Un conjunto V de puntos llamados vértices.
* Un conjunto de pares de vértices que se llaman aristas o arcos y que indican que vértices están relacionados.
De manera sencilla podemos decir que un grafo es un conjunto de vértices con enlaces entre ellos denominado aristas o arcos.
Un grafo simple es cuando entre dos vértices hay un solo arco, si hay más de un arco se llama multígrafo.
Un grafo es dirigido si los arcos se pueden recorrer en una dirección concreta y no en la contraria.
El grado de un vértice comprende el número de aristas que inciden en el vértice.
1) Maquina para venta de
refrescosESTADO ACTUAL:
CANTIDAD DE DINERO QUE SE HA
DEPOSITADO
ENTRADA ACTUAL: LA
MONEDA QUE SE DEPOSITA EN LA
MAQUINA:
DETERMINA LA SALIDA QUE EL
APARATO ENTREGA: NADA, CAMBIO,
REFRESCO O REFRESCO Y CAMBIO
2) Juegos de Pelea
Entradas: golpes,
agresiones, recuperaciones
Combiando con el estado: nivel de energía del
peleador
Efecto que se mantendrá
como salida: tambalearse,
caerse, cansarse, ser
noqueado, etc…
http://www.generation5.org/content/2003/FSM_Tutorial.asp
http://www.cs.princeton.edu/courses/archive/spr06/cos116/FSM_Tutorial.pdf
http://sakharov.net/fsmtutorial.htmlhttp://www.infovis.net/printMag.php?
num=137&lang=1http://chortle.ccsu.edu/FiniteAutomata/
index.html
top related