MATEMATICA DISCRETA

UNIVERSIDAD NACIONLA DE INGENERIA.
UNI.
TRABAJO DE MATEMATICA DISCRETA.
TEMA:AUTOMATAS.
DOCENTE: RENHE
FECHA:18 DE NOVIEMBRE DEL 2015.
GRUPO: 2M4-CO.
INTEGRANTES: KENVIN ANTONIO VALVERDE.
KAREN MARIAMERLO.
JOSE ANTONIO PAYAN.

AUTÓMATAS DETERMINISTAS.
Introducción
Los autómatas son una representación formal muy útil, que permite
modelar el comportamiento de diferentes dispositivos, máquinas,programas, etc.
Máquinas expendedoras de refrescos
El comportamiento de un programa (software)
El comportamiento de semáforos
 
La idea general consiste en modelar un sistema que:
Recibe un conjunto deelementos de entrada (estímulos)
Realiza algún proceso (cómputo)
Se produce una salida.

DEFINICIÓN AUTÓMATA

• Formalmente, un autómata finito determinista es una quíntupla (Q,Σ,δ, q0, F),
donde:
•Q: conjunto finito NO VACIO de estados
• Σ: alfabeto de entrada
• δ: Q x Σ ->Q, función de transición que especifica a qué estado pasa el
autómata desde el estado actual al recibir un símbolo deentrada. Esta función
se define para todas las parejas posibles de estados y de símbolos de entrada.
• δ(q,a) = q’ significa que del estado “q” con el símbolo “a”, el autómata pasa al
estado q’
• q0∈ Q:estado inicial de autómata
• F⊆ Q: conjunto de estados finales

AUTÓMATAS FINITOS DETERMINISTAS
• Ejemplo
• Considere un sistema formado por una lámpara y un interruptor. La
lámpara puede estarencendida o apagada. El sistema sólo puede
recibir un estímulo exterior: pulsar el interruptor. El funcionamiento es
habitual: si se pulsa el interruptor y estaba apagada la lámpara, se
pasa al estado deencendido, o si está encendida, pasa a pagada. Se
desea que la bombilla este inicialmente apagada.
• Considere que 0: encendido, 1: apagado y la única entrada posible
(pulsar interruptor) es “p”
• ¿Cómosería el autómata que representa a este sistema?

• Solución
• A = (Q, Σ, δ, q0, F), donde:
• Q = {0,1}
• Σ = {p}
• δ(0,p) = 1, δ(1,p) = 0
• q0 = 0
• F = {}
• Representación tabular
• En ocasiones...