“AUTOMATAS “
RODRIGO ESQUIVEL
RODRIGUEZ
7 “C” ING.MECATRONICA
PROGRAMACION AVANZADA
ING: JUAN ANTONIO PEREZ CELEDON
TEMAS:
ALGORITMOS DE PROGRAMACION EN TIEMPO REAL.
AUTOMATAS.
AUTOMATAS EN ESTADO FINITO DETERMINISTA.
AUTOMATAS EN ESTADO FINITO NO DETERMINISTA.
MAQUINAS DE TURING.
REDES DE PETRI.
Definición Formal de un Autómata
Un AF se representa como una 5-tupla: A = (Q, Σ, δ, q0, F). Donde: 1 Q: Un conjunto finito
de estados. 2 Σ: Un conjunto finito de símbolos de entrada (alfabeto) 3 q0: El estado
inicial/de comienzo. 4 F: cero o más´ estados finales/de aceptación´
Autómata ´: Conjunto de estados + Control → Cambio de estados en respuesta a una
entrada. Tipo de Control: Determinístico: Para cada entrada, hay solo un estado ´ al que el
autómata puede ir desde el estado en que se ´ encuentre. No determinístico: Un autómata
finito es ´ no-determinístico cuando se permite que el AF tenga 0 o más estados siguientes
para cada par ´ estado-entrada.
AUTOMATAS EN ESTADO FINITO DETERMINISTA.
El término máquina evoca algo hecho en metal, usualmente ruidoso y grasoso, que
ejecuta tareas repetitivas, que requieren de mucha fuerza o velocidad o precisión.
Ejemplos de éstas máquinas son las embotelladoras automáticas de refrescos. Su diseño
requiere de conocimientos en mecánica, resistencia de materiales y hasta dinámica de
fluidos. Al diseñar tal máquina, el plano en que se le dibuja hace abstracción de algunos
detalles presentes en la máquina real, tales como el color con que se pinta, o las
imperfecciones en la soldadura.
Al diseñar tal máquina, el plano en que se le dibuja hace abstracción de algunos detalles presentes
en la máquina real, tales como el color con que se pinta, o las imperfecciones en la soldadura.
El plano de diseño mecánico de una máquina es una abstracción de ésta, que e útil para
representar su forma física. Sin embargo, hay otro enfoque con que se puede modelar la máquina
embotelladora: cómo funciona, en el sentido de saber qué secuencia de operaciones ejecuta. Así,
la parte que introduce el líquido para por un ciclo repetitivo en que primero introduce un tubo en
la botella, luego descarga el líquido y finalmente sale el tubo para permitir la colocación de la
cápsula (corcholata).
El orden en que se efectúa este ciclo es crucial, pues si se descarga el líquido antes de haber
introducido el tubo en la botella, el resultado no será satisfecho. Las máquinas que estudiamos
son abstracciones matemáticas que capturan solamente el aspecto referente a las secuencias de
eventos que ocurren, sin tomar en cuenta ni la forma de la máquina ni sus dimensiones, ni
tampoco si efectúa movimientos rectos o curvos, etc.
Ahora es el momento de representar el concepto formal de autómata finito, con el fin de precisar
algunos de los argumentos y descripciones informales que se han visto anteriormente,
comenzaremos con el formalismo de un autómata finito determinista, que es aquel que sólo
puede estar en un único estado después de leer cualquier secuencia de entradas. El término
«determinista» hace referencia al hecho de que para cada entrada sólo existe uno y sólo un
estado al que el autómata puede hacer la transición a partir de su estado actual.
El término «Autómata Finito» hace referencia a la variedad determinista, aunque normalmente
utilizaremos el término «determinista», o la abreviatura AFD, con el fin de recordar el tipo de
autómata del que estamos hablando.
Un Autómata Finito Determinista consta de: 1.Un conjunto finito de estados, a menudo designado
como Q. 2.Un conjunto finito de símbolos de entrada, a menudo designado como ∑ (sigma). 3.Una
función de transición que toma como argumentos un estado y un símbolo de entrada y devuelve
un estado. La función de transición se designa habitualmente como ᵟ o Δ (delta). 4.Un estado
inicial, uno de los estados de Q. 5.Un conjunto de estados finales o de aceptación F. El conjunto F
es un subconjunto de Q.
A menudo haremos referencia a un autómata finito determinista mediante su acrónimo: AFD. La
representación más sucinta de un AFD consiste en un listado de los cinco componentes anteriores.
Normalmente, en las demostraciones, definiremos un AFD utilizando la notación de «quíntupla»
siguiente: A= ( Q, ∑ , Δ ,q0, F )
Autómatas en estado finito No-Deterministas
´ Si añadimos la propiedad de no-determinismo, no a ˜ nadimos ˜ poder al autómata.
Ósea que no podemos definir ningún´ lenguaje que no se pueda definir con el autómata ´
determinístico. Con la propiedad de no-determinismo se agrega eficiencia al describir una
aplicación: ´ Permite programar soluciones en un lenguaje de más´ alto nivel hay un
algoritmo para compilar un N-DFA en un DFA y poder ser ejecutado en una computadora
convencional, Extensión del N-DFA para hacer saltos de un estado a ´ otro
espontáneamente, con la cadena vacía () como entrada: N-DFA. Estos autómatas también
aceptan ´ lenguajes regulares.
Ejemplo
Un Autómata A que acepta ´ L = {x01y|x ∧ y ∈ {0, 1}
∗}
• El DFA acepta cadenas que tienen 01 en alguna parte
de la cadena
• El lenguaje del DFA es el conjunto de cadenas que
acepta {w|w tiene la forma “x01y” para algunas
cadenas x y y que consisten solo de 0’s y 1’s ´ }.
El autómata anterior puede ser representado con una tabla ´
de transiciones, definido como
A = ({q0, q1, q2}, {0, 1}, δ, q0, q1), de la siguiente forma:
01
→ q0 q2 q0
?q1 q1 q1
q2 q2 q1
Cada estado tiene un nodo asociado
• Cada transición de estados tiene un arco asociado ´
etiquetado con el/los símbolos correspondientes
• Existe una etiqueta de inicio para el estado inicial y un doble círculo asociado a los
estados finales
Por convención se utilizan: ´
• a, b, etc., o dígitos para los símbolos de entrada
• u, v, . . . , z para las cadenas de símbolos de entrada
• q, p, etc., para los estados
MAQUINAS DE TURING.
• Hasta ahora hemos visto clases de lenguajes relativamente simples
• Lo que vamos a ver ahora es preguntarnos que´ lenguajes pueden definirse por
cualquier equipo computacional
• Vamos a ver que pueden hacer las computadoras y los ´ problemas que no pueden
resolver, a los que llamaremos indecidibles.
Por ejemplo, podemos pensar en un programa de
computadora que imprima “hola” cuando encuentre un
entero positivo n > 2, que cumpla: x
n+y
n=z
n
, para
x, y y z enteros positivos
• La solución entera de la ecuación de arriba se conoce ´
como el ultimo teorema de Fermat, que llevo a los ´
matemáticos 300 a ´ nos resolver ˜
• El poder analizar cualquier programa de computadora y
decidir si va a imprimir un letrero como “hola” es en
general indecidible
• Lo que nos gustaría es tener una teoría de invencibilidad
basada en un modelo computacional sencillo (i.e.,
Máquina de Turing)
El propósito de la teoría de indecibilidad no es solo´
establecer cuales problemas son indecidibles, sino
también dar una gustaría sobre qué es lo que se puede ´
hacer o no con programación´
• También tiene que ver con problemas, que, aunque ´
sean decidibles, son intratables
• A finales del s. XIX y principios del s. XX, D. Hilbert
lanzo la pregunta abierta, si era posible encontrar un ´
algoritmo que determinara el valor de verdad de una
formula en l ´ lógica de primer orden aplicada a los ´
enteros.
• En 1931, K. Gödel probo su teorema de incompletas
para probar que no se podía construir dicho algoritmo.
• En 1936, A. Turing publico su maquina de Turing como ´
un modelo para cualquier tipo de computación (aunque ´
todavía no existían las computadoras)
• La hipótesis de Church o la tesis de Church-Turing dice ´
que lo que las maquinas de Turing (y para tal caso las ´
computadoras modernas) pueden computar son las
funciones recursivamente enumerables
• Una maquina de Turing consiste de un control finito que ´
puede estar en cualquier estado de un conjunto finito
de estados.
• Se tiene una cinta dividida en celdas, cada celda con
un símbolo.
• Inicialmente, la entrada (cadena finita de símbolos del
alfabeto) se coloca en la cinta, el resto de las celdas
tienen el símbolo especial vacío.
• La cabeza de la cinta esta siempre sobre una celda y al ´
principio esta sobre la celda m ´ as a la izquierda con el ´
primer símbolo de la cadena de entrada.
Un movimiento o transición puede cambiar de estado (o ´ quedarse en el estado actual), escribir
un símbolo (reemplazando el símbolo que existía o dejando el mismo) y mover la cabeza a la
izquierda o derecha.
REDES DE PETRI
Una red de Petri es un grafo orientado con dos tipos de nodos: lugares (representados
mediante circunferencias) y transiciones (representadas por segmentos rectos verticales).
Los lugares y las transiciones se unen mediante arcos o flechas. Automatización Industrial.
Un arco une siempre lugares con transiciones y nunca dos lugares o dos transiciones. Una
transición puede ser destino de varios lugares y un lugar puede ser el destino de varias
transiciones. Una transición puede ser origen de varios lugares y un lugar puede ser origen
de varias transiciones. Los lugares pueden presentar marcas (una marca se representa
mediante un punto en el interior del círculo). Transición Lugar Lugar Transición marca
Automatización Industrial. Cada lugar tiene asociada una acción o salida. Los lugares que
contiene marcas se consideran lugares activos. Cuando un lugar está activo sus salidas
están a uno. A las transiciones se les asocia eventos (funciones lógicas de las variables de
entrada). Una transición se dice que está sensibilizada cuando todos su lugares origen
están marcados. Cuando ocurre un evento asociado a una transición (la función lógica se
hace uno), se dice que la transición está validada. A B Salida A=1 Salida B=0 p1 p2
Transición sensibilizada p1 p2 p1 p2 p3 p4 Transición validada p5=1 LUGAR ACTIVO
TRANSICIÓN SENSIBILIZADA TRANSICIÓN VALIDADA Automatización Industrial. El marcado
cambia al franquear las transiciones. Para franquear una transición ha de estar validada y
sensibilizada Cuando una transición se franquea desaparecen las marcas de los lugares
origen y se añade una marca a cada uno de los lugares destino. a b C D C a Expresiones E
Booleanas D E a·b C=1 C a D E a·b FRANQUEO a =1 D=1; E=1 C a D E a·b FRANQUEO a ·b =1
C=1 Automatización Industrial. ejemplo: Cuando dos transiciones que están sensibilizadas
a la vez, pueden entrar en conflicto, ejemplo: Para que la red sea válida las condiciones de
validación t1 y t2 no pueden darse a la vez. t 1 t 2 t 1 t 1 t 2 t 2 t 1 t 2 t1=1 t1=1 t2=1 t 2 t 1
Automatización Industrial. Se pretende que el coche vaya de a hacia b y vuelva. Existe un
botón de puerta en marcha. En el inicio el coche está en a Entradas: m: puesta en marcha.
a : sensor llegada a izquierda. b : sensor llegada a derecha. Salidas: I : indica
desplazamiento a izquierda. D : indica desplazamiento a derecha. I D a b m
Automatización Industrial. En este caso las representaciones son iguales pero en
problemas más complejos la RdP se aproxima más al problema y trata mejor la ejecución
de tareas concurrentes. m b a D I RdP 0 1 D 2 I m b a Grafo . Se pretende que los dos
carritos de la figura, que en principio están en el lado izquierdo, vayan al extremo
derecho. El primero que llegue esperará al otro (sincronización). Después vuelven al lado
izquierdo donde el sistema se quedará en reposo cuando lleguen los dos carritos
(sincronización). Existen un botón de marcha m y dos sensores de llegada en cada lado a1
y a2 en el lado derecho y b1 y b2 en el lado izquierdo. Las señales de entrada son m, a1 ,
a2 , b1 y b2 las salidas son I1 , I2 , B1 , B2s a1 b1 a2 I 2 D2 b2 I 1 D1 m Automatización
Industrial. Cuando el marcado se traslada a estos lugares a la vez, las dos carritos están
listos para ponerse en marcha. b2 I 1 D1 m D2 I 2 a1 a2 (*) (*) b1 b1 × b 2 a1 × a 2 1 D1D2
4 2 3 D1 I 1 I 2 m b1 b2 b1 b2 b2 b1 b1 b2 b2b1 D2 5 I 2 6 I 1 a2a1 a2 a1 a1 a2 0 RdP
Tratamiento individual de procesos independientes. 2) Procesos paralelos o concurrentes.
3) Recursos compartidos. RECURSOS COMPARTIDOS Las RdP permiten modelar sistemas
donde un recurso es compartido por dos procesos de forma que el uso del recurso
durante la ejecución de un proceso impide que dicho recurso sea utilizado por el otro
proceso. Un recurso compartido se modela mediante un lugar con una marca inicial y
transiciones en conflicto t 2 t 1 Recurso Compartido Transiciones en conflicto Proceso 1
Proceso 2 Automatización Industrial. La validación consiste en comprobar que se cumplen
las propiedades de: - VIVACIDAD; LIMITACIÓN; REVERSIBILIDAD Hay que considerar : M0 :
marcado inicial. De este se desprende el comportamiento del sistema. [M0 ] : vector de
marcados posibles a partir de un marcado inicial. (marcados alcanzables). Ejemplo: L1 L2
L3 1 0 0 0 1 1 M0 = [ ] MARCADOS POSIBLES L1 L2 L3. Se trata de un concepto relacionado
con la idea de “no bloqueo”. Definición : Una transición se dice viva si para un marcado
inicial existe una secuencia de franqueos para la cual se puede franquear esa transición. Si
todas las transiciones de una red son vivas, la RdP se llama viva y así la red nunca se
bloquea. Ejemplo: Una red de Petri no viva. Para la secuencia de franqueos T1 , T2 , T1 , T2
, no hay bloqueo. Si ahora se franquean las transiciones T1 , T3 , T4 , ya no se puede
franquear ninguna transición más, la red queda “bloqueada”. T1 T2 T3 T4 Automatización
Industrial. Podemos tener redes pseudo-vivas en las que existen algunas transiciones vivas
y no se bloquea totalmente. Ejemplo: RdP Pseudovida. T2 T1 T4 T3 Sólo franqueamos al
comienzo, T1 después no se vuelve a franquear. Automatización Industrial. REDES DE
PETRI 16 Dpto. de Ingeniería Electrónica, de Sistemas Informáticos y Automática
Universidad de Huelva LIMITACIÓN: Definición : Se dice que la red está k- limitada si para
todo marcado alcanzable tenemos que ningún lugar tiene un número de marcas mayor
que k. Las redes 1-limitadas pueden implementarse mediante biestables, estas redes son
conocidas como binarias. Si la red diseñada generar más marcas que las que su limitación
permite el modelado será erróneo Ejemplo: Una red no limitada: PROCESO DE
PRODUCCIÓN Equivalente al problema productor-consumidor PROCESO DE CONSUMO
FIN DE PROCESO FIN CONSUMO INICIO CONSUMO Automatización Industrial. Una RdP es
reversible si para cualquier marcado alcanzable es posible volver al marcado inicial.
Ejemplo: Esta RdP es pseudovida, además no tiene la propiedad de reversibilidad ya que el
marcado inicial no se puede obtener jamás .
