LICENCIATURA EN INGENIERA EN COMPUTACIN

ICO 19

QUE PRESENTA:Miguel ngel Correa Gonzlez

PARA LA MATERIA DE:Autmatas y Lenguajes Formales

MAESTRO:Mtro. Hctor Caballero Hernndez

6 DE MARZO DE 2015

Autmata finito no determinista

Los autmatas son mquinas conceptuales para el reconocimiento de patrones. Son una representacin matemtica de un sistema que recibe una cadena de smbolos pertenecientes a un alfabeto determinado y determina si esa cadena es aceptada o no (si pertenece al lenguaje que reconoce el autmata).

Un Autmata Finito No Determinista (AFN) se define como una quntupla de la siguiente manera:

A=(Q,T,,q0,F)donde :

Q= Conjunto finito y no vaco de estados,

T= Alfabeto de entrada,

= Funcin de transicin que toma como argumentos un estado de Q y un smbolo de T, y devuelve un subconjunto de estados de Q.

q0= Subconjunto de Q que representa al conjunto de estados iniciales (a diferencia de losAFD, losAFNpueden admitir varios estados iniciales).

F= Subconjunto de Q que representa al conjunto de estados de aceptacin (estados finales).

Los Autmatas Finitos No Deterministas, tambin llamadosAFN, se caracterizan porque, a diferencia de losAFD, en un estado puede haber ms de una transicin posible para un mismo smbolo de entrada (alfabeto). Es decir /(q,a)/ 1 para algn "q" perteneciente a Q y para algn smbolo "a" perteneciente a T.

Ejemplo : Segn el siguiente autmata :

Donde (q0,01)=((q0,0),1)=({q0,q1},1)={q0,q1}.

Otra diferencia importante de losAFNcon respecto a losAFDes la posibilidad de tener ms de un estado inicial.

El lenguaje aceptado por unAFNes el conjunto de cadenas tales que despus de ser analizadas, elAFNha logrado alcanzar al menos un estado de aceptacin. Tales lenguajes de definen de la siguiente manera :

L(A) = {x perteneciente a T*/ (q0,x) interseccin F }.

Es importante establecer que para un lenguaje L aceptado por unAFN, entonces existe unAFDque tambin acepta el lenguaje L. Es por esto que se hace posible, a partir de unAFNdisear unAFDequivalente.

La operacin de calcular unAFDa partir de unAFNes muy comn y , por ello, se han desarrollado mtodos para hacerlo. El ms sencillo y eficiente es el siguiente :

1.- Se construye una tabla en la que cada columna est etiquetada con un smbolo del alfabeto de entrada y cada fila se etiqueta con un conjunto de estados.

2.- La primera fila se etiqueta con {q0}, y en cada entrada de la tabla se ponen los conjuntos de estados (P) a los que llevan lo smbolo correspondiente a la columna.

3.- Se etiqueta cada fila con cada uno de los conjuntos P que no tengan asociada una fila en la tabla (es decir, cada uno de los conjuntos P que aparezcan por primera ves en la tabla) y se completa cada una de estas filas con los correspondientes conjuntos de estados (P) a los que llevan los smbolos de cada columna.

4.- Se realiza el paso tres hasta que no hayan conjunto P sin filas asociadas.

5.- Se asocia a cada conjunto P que aparezca en la tabla un estado en el nuevoAFDy aquellos que tengan entre sus componentes algn estado final delAFNse considerarn estados finales en elAFD.

Ejemplo:Para el siguienteAFN:

AFDresultante:

Conclusin:Los Autmatas Finitos No Deterministas son modelos matemticos que permiten representar situaciones complejas de una manera ms directa, pero a la vez ms difcil de predecir, debido a que pueden estar en varios estados de manera simultanea, esto hace muy valioso tener un mtodo para transformar unAFNenAFD, para as obtener resultados ms manejables.

OPERACIONES CON CONJUNTOS

Las operaciones habituales que se definen sobre los conjuntos son:El conjunto llamado conjunto vacoo nulo, no tiene elementos. El conjunto vaco es un subconjunto de todos los conjuntos.La uninde conjuntosAyBse denota porA By es un conjunto formado por los elementos que aparecen enA, enBo en ambos.Por lo tantoA B={x|xA x B}.Por ejemplo, siA={1, 2, 3} yB= {a, b}, entoncesAB={1, 2, 3, a, b}.La interseccindeAyBes el conjunto de todos los elementos que aparecen simultneamente enAy tambin enB.Por lo tantoAB={x|xAy x B}.Por ejemplo, siA={1, 4, 5, 7} yB= {2, 4, 7, 8}, entoncesAB={4, 7}.El complemento relativosiAyBson dos conjuntos cualesquiera, el complemento deBcon respecto aAes el conjunto:A-B={x|xAy xB}.Por lo tanto,A-Besta compuesto por todos los elementos deAque no estn tambin enB. Por ejemplo, siA={0, 2, 4, 6, 8, 10} yB={0,1, 2, 3, 4}, entoncesA-B={6, 8, 10}, mientras queB-A={1, 3}.2A ,el conjunto potenciadeA, es el conjunto formado por todos los subconjuntos deA. Por ejemplo, seaA={a, b, c} . Entonces 2A ={ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.Dados dos conjuntosAyB, suproducto cartesiano,AxB, es el conjunto de todos los pares ordenados de los que el primer elemento proviene deAy el segundo deB. As que,AxB={(a, b)|aAy bB}. Por ejemplo, sA={1,2,3} yB={5,6} entonces:AxB={(1,5),(2,5),(3,5),(1,6),(2,6),(3,6)}.SiAyBson conjuntos y todos los elementos deAson tambin elementos deB, se escribeA By se dice queAes unsubconjuntodeB. Por ejemploA={1,2,3} yB={0,1,2,3,4,5} , se tieneA B. Por otro lado,Bno es un subconjunto deA, porque los elementos 0, 4 y 5 deBno lo son deA.La Inclusincuando cualquier elemento deAque este en B, o cualquier elemento de B que este en A, que sean iguales. Por ejemplo siA={2, 4, 5, 7, 8} yB={2, 4}, entoncesA B={2, 4}.La cardinalidadde un conjunto es el nmero de elementos de ese conjunto. Por ejemplo siA={a, b} entonces |A|=2. La cardinalidad del conjunto vaco es 0 porque no tiene ningn elemento.Para ver el grfico seleccione la opcin "Descargar" del men superiorTodos los conjuntos aqu tratados se consideran subconjuntos de un conjunto universal U. Los complementos pueden ser formados con respecto a este conjunto universal. SiAes un conjunto, entonces U-Aes el conjunto de todos los elementos que no estn en A. Conviene denotar tales complementos medianteA, de forma que U-A=A. Obsrvese que =U y U = .

EXPRESIONES REGULARES.Los lenguajes aceptados por un autmata finito se describen con facilidad mediante expresiones simples llamadas expresiones regulares.Sea S un alfabeto. La expresin regular sobre S y los conjuntos que denotan se definen de manera recursiva como sigue:1. es una expresin regular y denota al conjunto vaco.1. e es una expresin regular y denota al conjunto {e }.1. Para cada a S , a es una expresin regular y denota al conjunto {a}.1. Si r y s son expresiones regulares que denotan a los lenguajes R y S.; respectivamente, entonces tenemos lo siguiente:r+s es una expresin regular que denota a los conjuntos R S.(r) es una expresin regular que denota al conjunto R.rs es una expresin regular que denota a los conjuntos RS.r* es una expresin regular que denota al conjunto R*.r+ es una expresin regular que denota al conjunto R+.ries una expresin regular que denota al conjunto Ri.Ejemplo de Autmatas con sus expresiones regularesEl lenguaje del autmata de la figura 2.13. esta formado por cualquier cadena de 1s, incluyendo e .Para ver el grfico seleccione la opcin "Descargar" del men superiorFigura 2.13. La expresin regular del autmata es: 1*El lenguaje del autmata de la figura 2.14. esta formado por todas las cadenas de as de longitud par, incluyendo e .Para ver el grfico seleccione la opcin "Descargar" del men superiorFigura 2.14. La expresin regular del autmata es: (aa)*El lenguaje del autmata de la figura 2.15. esta formado por cadenas de cero ms as seguidas de cero ms bs.Para ver el grfico seleccione la opcin "Descargar" del men superiorFigura 2.15. La expresin regular del autmata es: a*b*.Existen muchas equivalencias con respecto a expresiones regulares basadas en las correspondientes igualdades de lenguajes. Por ejemplo sean r, s y t expresiones regulares sobre el mismo alfabeto S . Entonces:1. r + s = s + r2. (rs)t = r(st)3. (r + s)t = rt + st4. (r*)* = r*5. r(s + t) = rs + rt2.5. LENGUAJES REGULARES.Los lenguajes regulares pueden ser usados en la construccin de analizadores lxicos - programas que analizan un texto y extraen los lexemas ( o unidades lxicas) que hay en el mismo -.El conjunto de los lenguajes regulares sobre un alfabeto S esta formado por el lenguaje vaco, los lenguajes unitarios incluido {e } y todos los lenguajes obtenidos a partir de la concatenacin, unin y cerradura de estrella de lenguajes.Ejemplo de lenguajes regulares:Expresin RegularLenguaje Regular

10L={La cadena de 10}

1 + 0L={Una cadena de 0 una cadena de 1}

1*L={Cualquier cadena de 1s incluyendo e }

(00)*L={Cadenas de 0s de longitud par, incluyendo e }

0*1*L={Cadenas de ninguno o ms 0s concatenadas a cadenas de ninguno o ms 1s}

1(1 + 0)*L={Todas las cadenas sobre el alfabeto {1, 0} que empiecen con 1}

(1 + 0)*00L={Todas las cadenas sobre el alfabeto {1, 0} que terminen en 00}

(1 + 0)*00(1 + 0)*L={Cualquier combinacin de 0s 1s que contengan al menos dos ceros consecutivos}

Cuando sea necesario distinguir entre una expresin regular r y el lenguaje denotado por la misma, usaremos L(r) para denotar el lenguaje. En cualquier caso, si se afirma que w r, ello equivale a decir que w (r). Si r y s son expresiones regulares sobre el mismo alfabeto y si L(r)= L(s), entonces se dice que r y s son equivalentes. En el caso de que r y s sean equivalentes se puede escribir r= s. Tambin se puede usar r s en el caso de que L(r) L(s).2.6. FUNCIONES RECURSIVAS.Una definicin recursiva esta caracterizada por un proceso de tres pasos:1. Declaracin de los objetos bsicos que pertenecen al lenguaje (caso base).2. Otorgar las reglas para construir ms objetos a partir de los existentes (caso recursivo).3. Declarar que ningn otro objeto fuera de las dos reglas anteriores forman parte del lenguaje "Requisito de formalidad".Ejemplo: Encontrar una definicin recursiva para el lenguaje de todos los nmeros enteros divisibles a travs de 2, es decir, EVEN= {2, 4, 6, 8, ...}.1. 2 EVEN.2. x EVEN entonces x+2 EVEN.3. Ningn otro nmero que no sea obtenido por la regla 1 y la regla 2 EVEN.Para explicar est definicin se recorre la funcin recursiva, para demostrar que el nmero 14 EVEN:Por la regla 1 2 EVENPor la regla 2 2+2=4 EVENPor la regla 2 4+2=6 EVENPor la regla 2 6+2=8 EVENPor la regla 2 8+2=10 EVENPor la regla 2 10+2=12 EVENPor la regla 2 12+2=14 EVENEl anterior recorrido queda ms claro mediante figura 2.16.Para ver el grfico seleccione la opcin "Descargar" del men superiorFigura 2.16. Recorrido de la funcin recursiva, para demostrar que el nmero 14 EVEN.Sin embargo, la anterior definicin recursiva no es la nica, pueden adaptarse otras, por ejemplo:1. 2 EVEN.2. X,Y EVEN entonces X+Y EVEN.3. Ningn otro nmero EVEN.El recorrido de la funcin recursiva para el nmero 14 quedara de la siguiente forma:Por la regla 1 2 EVENPor la regla 2 x=2, y=2 entonces 2+2=4 EVENPor la regla 2 x=2, y=4 entonces 2+4=6 EVENPor la regla 2 x=4, y=4 entonces 4+4=8 EVENPor la regla 2 x=6, y=8 entonces 6+8=14 EVENEsta segunda definicin recursiva es mejor que la primera porque se obtiene el resultado en un menor nmero de pasos como se observa en la figura 2.17.Para ver el grfico seleccione la opcin "Descargar" del men superiorFigura 2.17. Recorrido de la segunda funcin recursiva, para demostrar que el nmero 14 EVEN.La definicin recursiva que se obtenga depender de dos casos:1. Que tan fcil de entender es la definicin recursiva.2. Los tipos de teoremas que se desean demostrar.2.7. PUMPING LEMMA O LEMA DE BOMBEO PARA LENGUAJES REGULARES.Si L es un lenguaje finito, es regular y se podr construir un autmata finito o una expresin regular para ellos de forma sencilla. Tambin, siLes especificado ya sea por medio de un autmata finito o una expresin regular, la respuesta es obvia. Por desgracia, hay relativamente pocos lenguajes que sean regulares y, en el caso de un lenguaje infinito, la bsqueda exhaustiva de una expresin regular o un autmata finito puede resultar intil. En este caso, se necesita obtener algunas propiedades que compartan todos los lenguajes regulares infinitos y que no estn presentes en los lenguajes regulares.Supongamos que un lenguaje es regular y que, por tanto, es aceptado por un DFA M=(Q, S , q0, d , F), donde Q contienenestados. SiL(M) es infinito, podremos encontrar cadenas cuya longitud sea mayor quen. Supongamos quew= a1, a2, ...,an+1 es una de las cadenas de longitudn+1 que pertenecen a L(M).Si tuviramosq1= d (q0, a1)q2= d (q1, a2)y as sucesivamente, obtendramos losn+1 estados, q1, q2 ,..., qn+1. Puesto que Q contiene slonestados , los qino sern todos distintos.En consecuencia, para algunos ndicesjyk, con 1j n+1, se obtendr que qj= qk. Por lo tanto, tendremos un ciclo en el camino que parte de q0 hasta un estado de aceptacin segn se muestra en la figura 2.18.Para ver el grfico seleccione la opcin "Descargar" del men superiorFigura 2.18.Puesto quej