Parcial 2 Flashcards
Automata finito
Reconocen lenguajes regulares (de tipo 3) y se pueden representar como una cinta y una cabeza de lectura.
La cinta de entrada solo contiene simbolos de un determinado alfabeto, y se mueve en una sola direccion.
El control de estados determina el funcionamiento del automata (cabezal).
Una sentencia es reconocida por este automata si el control de estados llega a un estado final.
Definicion formal:
Es una septupla:
AF = {E,Q,f,q1,F} (raro, son cinco no 7)
E=conjunto finito de simbolos de entrada, que constituye el vocabulario
Q=conjunto finito de estados
f: E x Q –> Q es la funcion de transicion
q1 ∈ Q es el estado inicial
F ⊂ Q es el conjunto de estados finales
Igual que con los otros, hay teoremas que dicen que toda gramatica regular genera un lenguaje regular que un automata finito puede reconocer.
De la misma forma, para todo automata finito existe una gramatica tal que el lenguaje generado por ella es reconocido por el automata finito
Automatas finitos deterministas vs no deterministas
un AF es D o ND segun su funcion de transicion f, que puede ser determinista o no.
Un AFND se caracteriza porque dada una entrada e en un estado qi, se puede pasar a otro estado qj,qk,..,qn sin poder saber a ciencia cierta a cual pasara, mientras que en un AFD esto no sucede, dada una entrada e siempre hay un solo estado posible al que pasara el automata.
AFND
Formalmente, su definicion es igual a la del AFD, pero cambia la definicion de f, que ahora pasa a ser no determinista, es decir
f:E* x Q –> P(Q), donde P(Q) es el conjunto potencia de Q, es decir el conjunto de estados posibles.
qi es el estado inicialm pero puede no ser unico en este caso
Teorema sobre transformacion de AFND en AFD
Para todo AFND se puede construir un AFD tal que ambos reconozcan el mismo lenguaje
Transformacion de expresion regular en automata finito
Dada una expresion regular existe un AF capaz de reconocer el lenguaje que esta define, y viceversa, dado un AF, existe una regex que genera el lenguaje que este reconoce.
Redes de petri (usos)
Se usan para modelar una gran variedad de fenomenos (de informatica y control)
Permiten modelar y visualizar comportamientos con paralelismo, concurrencia, sincronizacion e intercambio de recursos.
Plaza, transicion y arco
Una PN tiene nodos y arcos.
Los nodos pueden ser plazas, representadas con circulo (su cantidad es finita y no cero), o bien transiciones, representadas con barras (su cantidad tambien es finita y no cero)
Los arcos se representan con flechas y pueden tener dos direcciones, desde una plaza a una transicion o de una transicion a una plaza (no es valido un arco de una transicion a otra transicion por ejemplo).
P = {P1, P2, P3, ….. , Pn} es el conjunto de plazas
T = {T1, T2, T3, …… , Tn} es el conjunto de transiciones
Transicion sin lugar (plaza) de entrada es una fuente
Transicion sin lugar (plaza) de salida es un sumidero
Marcado de plaza y de red
Cada plaza contiene un numero entero de tokens o marcas
m(Pi) = mi
Ademas, podemos definir la marca m de la red, como el vector que contiene las marcas de cada plaza
m = (m1, m2, m3, …. , mn)
A esta marca de la red tambien se la conoce como estado
Este marcado de la red representa el estado de la PN en un momento dado, y a su vez la evolucion de la red esta correspondida a una evolucion del marcado.
Disparo de transicion
Si las condiciones se cumplen, la transicion se dispara y el estado de la red cambia.
Condicion: Para que una transicion se dispare primero debe estar sensibilizada, es decir, que cada plaza de entrada a la transicion tiene que tener al menos el mismo numero de tokens que el peso del arco que las conecta con la transicion.
Disparo: consume los tokens necesario de las plazas que entran (segun el peso de los arcos), y genera tokens a las plazas de salida de la transicion.
Cabe aclarar que los disparos son atomicos, y tienen duracion cero.
PN autonoma vs no autonoma
Cuando una PN evoluciona por los disparos de sus transiciones, cuyos instantes de disparo son desconocidos o no estan indicados, la PN es autonoma.
Por otro lado, cuando una transicion se dispara porque se cumplen las condiciones de sensibilizado y esta asociada a un evento externo, la PN es no autonoma. Es decir, este tipo de PN describe un sistema cuya evolucion esta condicionada a un evento externo
Pn especiales/particulares
PN tienen alta complejidad, por lo que para facilitar su analisis se aplican restricciones en la estructura grafica de la red, obteniendo asi distintos casos particulares
PN ordinaria
Se caracteriza porque todos sus arcos son de peso unitario. Es una restriccion estructural
Formalmente, es la tupla
N = (P, T, F)
P es el conjunto de lugares o plazas
T es el conjunto de transiciones
F ⊆ (P x T) U (T x P) es el conjunto de arcos de transicion
Arcos de salida de transicion (T x P), (t°) el puntito es negro relleno
Arcos de entrada de transicion (P x T) (°t)
Una marca μ de N es un mapa μ: P->N
μ0 es la marca inicial
Una PN ordinaria N se denota (N,μ0)
Maquina de estado (SM de State Machine)
Es una PN ordinaria en la que cada transicion tiene un lugar de entrada y uno de salida.
PN sin marcar es grafico de estado sii cada transicion tiene una plaza de entrada y una de salida.
Hay que notar que para que este tipo de red se comporte como una maquina de estado (automata), el marcado debe ser el adecuado. Es decir que solo puede tener un token (equivale al automata que esta en un estado a la vez).
Chequear imagenes para vislumbrar esto
Grafo de Marcado (MG) (eventos)
Mg es una PN ordinaria tal que cada lugar tiene una transicion de entrada y una transicion de salida.
Esto significa que no puede haber conflicto, pero si concurrencia.
Los MG se utilizan generalmente para representar operaciones simultaneas
En un grafico de estado (marcado) puede haber conflictos, pero no hay sincronizacion (es decir, una transicion con al menos dos lugares de entrada). En un grafico de eventos puede haber sincronizaciones, pero no hay conflictos.
Conflicto en una PN
Un conflicto (estructural) se da cuando una plaza tiene mas de una transicion de salida, por lo que no se pueden disparar ambas, se debe “optar” por una de ellas.
PN libre de conflicto
Esta PN no tiene conflictos, cada lugar tiene como maximo una transicion de salida.
Vivacidad y accesibilidad son decidibles para estas redes.
Hay una constante c tal que para una marca inicial con x tokens, la marca maxima de cada lugar es ilimitada o esta limitada por cx.
PN de libre eleccion (FC)
FC PN es una PN que cumple la siguiente condicion:
Para cada conflicto P1,{T1,T2,….} ninguna de las transiciones T1, T2, …. posee otro lugar de entrada que P1.
Una PN de libre eleccion extendida es tal que para cada conflicto P1,{T1,T2,….} todas las transiciones T1, T2, …. tienen el mismo conjunto de lugares de entrada. Es decir, si T1 tiene P1 y P2 como lugares de entrada, estos tambien son lugares de entrada de T2
PN simple
Es una PN en la que cada transicion solo puede verse afectada por un conflicto como maximo.
Si existe una transicion T1 y dos conflictos, por ejemplo P1,{T1,T2} y P2{T1,T3} la red ya no es simple
Auto loop
Un par Pi Tj se llama auto-loop si Pi es un lugar de entrada y salida de Tj.
Es como un ciclo infinito basicamente.
Se suelen usar para sincronizar disparos de una transicion. Supongamos que en una plaza tengo 5 tokens y un arco de peso 4. Si quiero limitar la transicion para que no consuma lo 4 tokens juntos puedo poner un auto-loop que me va a limitar la transicion a un token por vez
Igual solemos buscar evitarlos, ya que es complicado llevarlos a codigo despues
PN pura
Una PN es pura si no tiene auto-loops
Propiedad importante: todas las PN impuras se pueden convertir en PN puras.
Extensiones de las PN
Son reglas agregadas para enriquecer la capacidad del modelo, para tratar problemas mas complejos.
No todas las propiedades de las PN ordinarias se mantienen para las extensiones
Generalizacion de una PN ordinaria
Se le asocia un peso a cada arco, que puede ser distinto de 1. El peso de un arco me dice cuantos tokens va a consumir la transicion al dispararse, o cuantos va a generar, dependiendo el caso (entrada o salida de una plaza).
Todas las PN generalizadas se pueden transformar en ordinarias, pero la transformacion suele ser complicada
PN de capacidad finita
En las PN ordinarias las plazas tienen capacidad infinita, ahora en las generalizadas, podemos tener una capacidad finita.
Es decir que se asocia un numero entero positivo a una plaza, que indica el maximo numero de tokens que puede almacenar.
Ahora, si el disparo de una transicion genera un numero mayor de tokens a la capacidad de una plaza, esta no se puede disparar.
Toda capacidad finita de una plaza en una PN se puede transformar en una PN ordinaria.
PN coloreadas
Tienen tokens de diferentes colores
Son de gran valor para modelar sistemas complejos
Todas las PN coloreadas con un numero finito de colores se pueden convertir en PN ordinarias.
PN extendidas
Tienen arcos especiales llamados inhibidores
Si el peso de un arco inhiidor Pi->Tj es s, la transicion Tj se habilita solo si m(Pi) < s, es decir es una prueba de umbral.
El caso de s=1 es un caso particular importante, llamado prueba a cero. Puesto que la transicion Tj solo se habilita si m(Pi)=0, es decir si la plaza esta vacia.
En general, las PN extendidas no se pueden convertir en ordinarias
Pn con prioridades
Este tipo de red se una cuando deseamos elegir entre una cantidad de transiciones habilitadas, esta formada por:
Una red de petri
Y una relacion de orden parcial en las transiciones de la red.
Es decir que cuando hay transiciones que tiene conflicto entre ellas, se setea una prioridad de disparo
Todas las PN prioritarias se pueden modelar como PN extendidas (pero ojo, aca estariamos acoplando la logica con las politicas, no seria recomendable)
Politicas y logica de PN
La logica es la que esta dada por la estructura y el estado de la red, mientras que las politicas nos dicen como se comporta ante conflictos (prioridades).
Es importante separar las politicas de la logica, para garantizar escalabilidad a futuro. Si acoplo las politicas en la logica de la PN, a futuro me generara problemas si deseo cambiar algo, ademas de que sera mas dificil pasar al codigo
