Talf

• Para q € Q y        €        se define: d(q,       )={p /hay una transicion d q a p etiquetada con        } • d(q,      ) es la coleccion d estados q "siguen" directamente a q pasando por la transicion etiquetada con        • EJEMPLO:






PASO DE AFN CON TRANSI. EPSYLON A AFN SIN TRANSI. EPSYLON: 1) Calcular el Epsylon-cierre d todos los estados 2) Dibujar el automata inicial sin transiciones 3) Poner las transiciones:        (q,       )=      - c [d(     - c(q),      ) ] =  {p₁, p₂,...,p_n} . Dibujamos flechas con el simbolo       desde q hasta todos los p_i (i=1, ... , n) --> Esto se hace para TODOS los ESTADOS (y en cada estado se hace con TODOS los SIMBOLOS)









2.8 AUTOMATAS FINITOS Y EXPRESIONES REGULARES ER -> AF: Casos base: 1)        :                  2)         :                                            3) a €        :                                           • Casos recursivos: teniendo dos ER r y s --> L(r)=L(m1) donde m1=(Q₁,        ,s₁,        , F₁) ; L(s)=L(m2) donde m2=(Q₂,       ,S₂,       ,F₂) •

AF -> ER: el conjunto d lenguajes aceptados por un AF sobre el alfabeto       contiene         y los lenguajes unitarios {a} para todo a €        . Este conjunto es cerrado con respecto a la union, concatenacion y cerradura estrella • Teorema de Kleene: todo lenguaje regular es aceptado por un  AF y todo lenguaje aceptado por un AF es tb un lenguaje regular • Consideramos el AF M=(Q,       ,s,F,        ) y supongamos q s=q₀ es el estado inicial. Para todo estado q_i, sea: A_i={w €        /         (q_i,w)       F              } // Es decir A_i es lo q se acepta desde q_i // Observese q A₀=L(M) // Se advierte tb que es posible q A_i =      // Si q_i € F, entonces se obtiene q       € A_i • Lema de Arden: X = A · X U B donde             A tiene una solucion unica, X = A^*B 












2.9 PROPIEDADES DE LOS LENG. REGULARES ¿Cuando un lenguaje L es regular? 1) si L es finito, L es regular 2) cuando existe una ER r tal que L(r)=L 3) cuando existe un AF M tal que L(M)=L  • NOTA: Para probar q un lenguaje es regular --> construir el automata o dar la expresion regular // Para probar que un lenguaje NO es regular usar lema del bombeo • Suponemos q trabajamos con un lenguaje regular: AFD m=(Q,       ,q₀,        ,F) // L(M) es infinito (nos dice q habra lazos d realimentacion, cierre + o cierre *) // w=a₁a₂....a_n+1 // w € L(m) // |w|=n+1 > n // q₀,q₁,.....,q_n+1 camino d aceptacion, n+1 estados, entonces repite algun n estados en Q // w=a₁a₂....a_n+1 € L(m) // w^'=a₁a₂....a_ja_k+1a_k+2......a_na_n+1 € L(m) • LEMA DEL BOMBEO: sea L un lenguaje regular infinito, entonces existe una constante k asociada al lenguaje, tal que: si w es una cadena de L cuya longitud es mayor o igual, (|w|>=k), w se puede descomponer de la forma w=uvx donde: |v|>=1,|uv|<=k, y todas las cadenas d la forma uvⁱx € L, para todo i >=0 // El lema del bombeo tiene una propiedad q debe tener todo lenguaje regular y nos facilita una forma d determinar si un lenguaje no es regular. Para demostrarlo se mostrara q para cualquier valor n lo bastante grande, se tendra al menos una cadena d longitud n o mayor q falle al ser bombeada • El lema del bombeo no dice si un lenguaje es regular, nos dice si NO lo es encontrando un contraejemplo.• Teorema: sea M un AF con k estados: 1)L(M)           <=> M acepta una cadena d longitud menos q k 2)L(M) infinito <=> M acepta una cadena d longitud n, donde k<=n<2k // En la practica es mas sencillo dado un automata M: 1)Suprimimos todos aquellos estados desde los q  no hay un camino hasta un estado final. Si suprimi el estado inicial, entonces L(M) =        2)Suprimimos los sumideros. Si aun asi hay ciclos (lazos) entonces L(M) es infinito • Para hallar el complementario de un lenguaje regular (q tb es regular) podemos construir el AFD del lenguaje original y luego hallar el de su complementario cambiando estados finales por no finales y viceversa.